Leetcode 1697. Checking Existence of Edge Length Limited Paths #158
Description
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算法的步骤：
- 完成UnionSet类，核心方法是初始化、寻找根节点和合并两点集合。
- 对题目条件的边排序
- 依次遍历边，讲点一个个连接起来
此外，因为查询数组长度过大，这道题也需要对查询数组排序。这是充分利用并查集特性，找到查询数组规律，优化算法。
这道题是对该算法的改进，对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;
}
}
}