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)
1import java.util.*;
2
3class UnionFind {
4 int[] parent, rank;
5 public UnionFind(int size) {
6 parent = new int[size];
7 rank = new int[size];
8 for (int i = 0; i < size; i++) {
9 parent[i] = i;
10 rank[i] = 1;
11 }
12 }
13 public int find(int u) {
14 if (u != parent[u]) {
15 parent[u] = find(parent[u]);
16 }
17 return parent[u];
18 }
19 public void union(int u, int v) {
20 int rootU = find(u);
21 int rootV = find(v);
22 if (rootU != rootV) {
23 if (rank[rootU] > rank[rootV]) {
24 parent[rootV] = rootU;
25 } else if (rank[rootU] < rank[rootV]) {
26 parent[rootU] = rootV;
27 } else {
28 parent[rootV] = rootU;
29 rank[rootU]++;
30 }
31 }
32 }
33 public boolean connected(int u, int v) {
34 return find(u) == find(v);
35 }
36}
37
38public class Solution {
39 public boolean[] edgeLengthLimitedPaths(int n, int[][] edgeList, int[][] queries) {
40 UnionFind uf = new UnionFind(n);
41 boolean[] answers = new boolean[queries.length];
42 Arrays.sort(edgeList, Comparator.comparingInt(a -> a[2]));
43
44 int[][] indexedQueries = new int[queries.length][];
45 for (int i = 0; i < queries.length; i++) {
46 indexedQueries[i] = new int[] { queries[i][0], queries[i][1], queries[i][2], i };
47 }
48 Arrays.sort(indexedQueries, Comparator.comparingInt(a -> a[2]));
49
50 int edgeIndex = 0;
51 for (int[] q : indexedQueries) {
52 int p = q[0], q2 = q[1], limit = q[2], qIndex = q[3];
53 while (edgeIndex < edgeList.length && edgeList[edgeIndex][2] < limit) {
54 uf.union(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
55 edgeIndex++;
56 }
57 answers[qIndex] = uf.connected(p, q2);
58 }
59
60 return answers;
61 }
62}In this Java solution, Union-Find is used with path compression similar to the other language implementations. The solution sorts edgeList and queries by their limits and processes each query by updating union information of edges whose distances are less than the query's limit. This allows for efficiently answering the connected component queries.
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
By extending Kruskal's approach in JavaScript, this implementation sorts edge and query constraints individually. Ensuring correct union-find updates, it verifies connectivity under query-specific conditions effectively.