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 constructor(size) {
3 this.parent = Array.from({ length: size }, (_, index) => index);
4 this.rank = Array(size).fill(1);
5 }
6 find(u) {
7 if (u !== this.parent[u]) {
8 this.parent[u] = this.find(this.parent[u]);
9 }
10 return this.parent[u];
11 }
12 union(u, v) {
13 const rootU = this.find(u);
14 const rootV = this.find(v);
15 if (rootU !== rootV) {
16 if (this.rank[rootU] > this.rank[rootV]) {
17 this.parent[rootV] = rootU;
18 } else if (this.rank[rootU] < this.rank[rootV]) {
19 this.parent[rootU] = rootV;
20 } else {
21 this.parent[rootV] = rootU;
22 this.rank[rootU]++;
23 }
24 }
25 }
26 connected(u, v) {
27 return this.find(u) === this.find(v);
28 }
29}
30
31function edgeLengthLimitedPaths(n, edgeList, queries) {
32 const uf = new UnionFind(n);
33 const answers = new Array(queries.length).fill(false);
34 edgeList.sort((a, b) => a[2] - b[2]);
35 const indexedQueries = queries.map((q, index) => [...q, index]).sort((a, b) => a[2] - b[2]);
36
37 let edgeIndex = 0;
38 for (const [p, q, limit, qIndex] of indexedQueries) {
39 while (edgeIndex < edgeList.length && edgeList[edgeIndex][2] < limit) {
40 uf.union(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
41 edgeIndex++;
42 }
43 answers[qIndex] = uf.connected(p, q);
44 }
45
46 return answers;
47}The JavaScript implementation utilizes the Union-Find data structure to organize and process the sorted edges and queries. This approach simplifies determining if two nodes, specified in a query, are connected through edges that satisfy the distance constraint provided by the query's limit.
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
This Java solution employs a method aligned with Kruskal's algorithm where queries are answered after processing all relevant edges for each query limit, ensuring a correct span before checking connectivity.