Sponsored
Sponsored
This approach is based on using a Union-Find (Disjoint Set Union) data structure, which allows us to efficiently keep track of connected components in the graph. The strategy involves sorting both the edges and the queries based on the edge weights and the query limits, respectively. By processing these sorted lists, we can incrementally add edges to the Union-Find structure and query the connectivity status effectively.
Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)
1class UnionFind:
2 def __init__(self, size):
3 self.parent = list(range(size))
4 self.rank = [1] * size
5
6 def find(self, u):
7 if u != self.parent[u]:
8 self.parent[u] = self.find(self.parent[u])
9 return self.parent[u]
10
11 def union(self, u, v):
12 rootU = self.find(u)
13 rootV = self.find(v)
14 if rootU != rootV:
15 if self.rank[rootU] > self.rank[rootV]:
16 self.parent[rootV] = rootU
17 elif self.rank[rootU] < self.rank[rootV]:
18 self.parent[rootU] = rootV
19 else:
20 self.parent[rootV] = rootU
21 self.rank[rootU] += 1
22
23 def connected(self, u, v):
24 return self.find(u) == self.find(v)
25
26
27def edgeLengthLimitedPaths(n, edgeList, queries):
28 uf = UnionFind(n)
29 answers = [False] * len(queries)
30 edgeList.sort(key=lambda x: x[2])
31 sorted_queries = sorted(enumerate(queries), key=lambda x: x[1][2])
32
33 edgeIndex = 0
34 for qIndex, (p, q, limit) in sorted_queries:
35 while edgeIndex < len(edgeList) and edgeList[edgeIndex][2] < limit:
36 uf.union(edgeList[edgeIndex][0], edgeList[edgeIndex][1])
37 edgeIndex += 1
38 answers[qIndex] = uf.connected(p, q)
39
40 return answersThis Python code implements the Union-Find with Path Compression technique. Initially, we sort the edgeList by distance and the queries by their limit. As we iterate over each query, we add edges to the Union-Find structure that are below the given query's limit. Then, we check if the specified nodes in the query belong to the same connected component.
This approach involves modifying Kruskal's Minimum Spanning Tree algorithm to answer multiple queries about path existence. We leverage the intrinsic nature of Kruskal's algorithm which builds an MST (or a union-find structured graph) incrementally. For each query sorted by limit, we add edges with weight less than the limit to the union-find structure and check if two nodes are connected.
Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)
1#include <algorithm>
#include <numeric>
class UnionFind {
public:
std::vector<int> parent, rank;
UnionFind(int size) : parent(size), rank(size, 1) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int u) {
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}
void union_sets(int u, int v) {
int rootU = find(u);
int rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] > rank[rootV])
parent[rootV] = rootU;
else if (rank[rootU] < rank[rootV])
parent[rootU] = rootV;
else {
parent[rootV] = rootU;
++rank[rootU];
}
}
}
bool connected(int u, int v) {
return find(u) == find(v);
}
};
std::vector<bool> edgeLengthLimitedPathsKruskal(int n, std::vector<std::vector<int>>& edgeList, std::vector<std::vector<int>>& queries) {
UnionFind uf(n);
std::vector<bool> answers(queries.size(), false);
std::sort(edgeList.begin(), edgeList.end(), [](const std::vector<int>& a, const std::vector<int>& b) { return a[2] < b[2]; });
std::vector<std::pair<int, std::vector<int>>> sorted_queries;
for (int i = 0; i < queries.size(); ++i) {
sorted_queries.emplace_back(i, queries[i]);
}
std::sort(sorted_queries.begin(), sorted_queries.end(), [](const std::pair<int, std::vector<int>>& a, const std::pair<int, std::vector<int>>& b) { return a.second[2] < b.second[2]; });
int edgeIndex = 0;
for (const auto& [qIndex, qry] : sorted_queries) {
int p = qry[0], q = qry[1], limit = qry[2];
while (edgeIndex < edgeList.size() && edgeList[edgeIndex][2] < limit) {
uf.union_sets(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
++edgeIndex;
}
answers[qIndex] = uf.connected(p, q);
}
return answers;
}Using C++, this solution modifies Kruskal's algorithm, concurrently managing component union information while sorting through the graph's edges and query constraints. It ensures each query's conditions are met before assessing component connectivity.