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)
1using System;
2using System.Linq;
3
4public class UnionFind {
5 private int[] parent;
6 private int[] rank;
7
8 public UnionFind(int size) {
9 parent = new int[size];
10 rank = new int[size];
11 for (int i = 0; i < size; i++) {
12 parent[i] = i;
13 rank[i] = 1;
14 }
15 }
16
17 public int Find(int u) {
18 if (u != parent[u]) {
19 parent[u] = Find(parent[u]);
20 }
21 return parent[u];
22 }
23
24 public void Union(int u, int v) {
25 int rootU = Find(u);
26 int rootV = Find(v);
27 if (rootU != rootV) {
28 if (rank[rootU] > rank[rootV]) {
29 parent[rootV] = rootU;
30 } else if (rank[rootU] < rank[rootV]) {
31 parent[rootU] = rootV;
32 } else {
33 parent[rootV] = rootU;
34 rank[rootU]++;
35 }
36 }
37 }
38
39 public bool Connected(int u, int v) {
40 return Find(u) == Find(v);
41 }
42}
43
44public class Solution {
45 public bool[] EdgeLengthLimitedPaths(int n, int[][] edgeList, int[][] queries) {
46 var uf = new UnionFind(n);
47 bool[] answers = new bool[queries.Length];
48 Array.Sort(edgeList, (a, b) => a[2].CompareTo(b[2]));
49
50 var indexedQueries = queries.Select((q, index) => new { q, index }).OrderBy(x => x.q[2]).ToArray();
51
52 int edgeIndex = 0;
53 foreach (var item in indexedQueries) {
54 int p = item.q[0], q = item.q[1], limit = item.q[2], qIndex = item.index;
55 while (edgeIndex < edgeList.Length && edgeList[edgeIndex][2] < limit) {
56 uf.Union(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
57 edgeIndex++;
58 }
59 answers[qIndex] = uf.Connected(p, q);
60 }
61
62 return answers;
63 }
64}The C# solution uses a similar approach with Union-Find to efficiently handle path inquiries. Edges and queries are sorted by weight constraints, and queries check for connectivity using updated Union-Find based on the processed edges.
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)
1using System.Linq;
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int Find(int u) {
if (u != parent[u]) {
parent[u] = Find(parent[u]);
}
return parent[u];
}
public void Union(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]++;
}
}
}
public bool Connected(int u, int v) {
return Find(u) == Find(v);
}
}
public class Solution {
public bool[] EdgeLengthLimitedPathsKruskal(int n, int[][] edgeList, int[][] queries) {
var uf = new UnionFind(n);
bool[] answers = new bool[queries.Length];
Array.Sort(edgeList, (a, b) => a[2].CompareTo(b[2]));
var indexedQueries = queries.Select((q, index) => new { q, index }).OrderBy(x => x.q[2]).ToArray();
int edgeIndex = 0;
foreach (var item in indexedQueries) {
int p = item.q[0], q = item.q[1], limit = item.q[2], qIndex = item.index;
while (edgeIndex < edgeList.Length && edgeList[edgeIndex][2] < limit) {
uf.Union(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
edgeIndex++;
}
answers[qIndex] = uf.Connected(p, q);
}
return answers;
}
}This C# solution utilizes Kruskal's algorithm methodology, aligning edge addition with sorted queries. It incrementally processes connections, ensuring query constraints are met before node connectivity checks.