Leetcode 1697. Checking Existence of Edge Length Limited Paths

[Woodyiiiiiii]

1697. Checking Existence of Edge Length Limited Paths

类似问题

• 1631. Path With Minimum Effort
• 2421. Number of Good Paths
• 1319. Number of Operations to Make Network Connected
• 839. Similar String Groups
• 1579. Remove Max Number of Edges to Keep Graph Fully Traversable

这道题一开始想用DFS来做，发现TLE了(DFS最好情况也是O(n))。复杂度在于如何用小于O(n)的时间内找到一个节点能否有严格小于某个值的路径到另一个节点。

那只能用并查集Union Find算法了，能保证时间复杂度是O(lgn)级别。

Union Find算法的步骤：

1. 完成UnionSet类，核心方法是初始化、寻找根节点和合并两点集合。
2. 对题目条件的边排序
3. 依次遍历边，讲点一个个连接起来

此外，因为查询数组长度过大，这道题也需要对查询数组排序。这是充分利用并查集特性，找到查询数组规律，优化算法。

这道题是对该算法的改进，对query数组和边数组排序，然后对query数组遍历，依次找到符合条件的边，连通起来，判断是否两点存在同一个集合内。

class Solution {

    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        // sort edgeList by weight
        Arrays.sort(edgeList, Comparator.comparingInt(o -> o[2]));
        // sort queries by weight
        int[][] newQueries = new int[queries.length][4];
        for (int i = 0; i < queries.length; ++i) {
            newQueries[i] = new int[]{queries[i][0], queries[i][1], queries[i][2], i};
        }
        Arrays.sort(newQueries, Comparator.comparingInt(o -> o[2]));

        // union find
        UnionSet unionSet = new UnionSet(n);
        boolean[] ans = new boolean[queries.length];
        int idx = 0;

        for (int i = 0; i < queries.length; i++) {
            int[] query = newQueries[i];
            int u = query[0];
            int v = query[1];
            int limit = query[2];
            while (idx < edgeList.length && edgeList[idx][2] < limit) {
                unionSet.merge(edgeList[idx][0], edgeList[idx][1]);
                idx++;
            }
            ans[query[3]] = unionSet.find(u) == unionSet.find(v);
        }

        return ans;
    }

    static class UnionSet {
        int n;
        int[] parent;
        int[] rank;

        public UnionSet(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            rank = new int[n];
            Arrays.fill(rank, 1);
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean merge(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return true;
            }

            if (rank[rootX] < rank[rootY]) {
                int tmp = rootX;
                rootX = rootY;
                rootY = tmp;
            }

            parent[rootY] = rootX;
            rank[rootX] += rank[rootY];
            return false;
        }
    }

}

---

• https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/description/
• https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/solutions/1192227/java-clean-union-find-solution-with-detailed-comments/?languageTags=java