Sponsored
Sponsored
This approach utilizes the Union-Find (or Disjoint Set Union, DSU) data structure to detect cycles. The key operations in Union-Find are 'find', which determines the representative of a set, and 'union', which merges two sets. When processing each edge, we attempt to unite the vertices. If both vertices are already in the same set, a cycle is detected, and this edge is the redundant one.
Time Complexity: O(n) where n is the number of edges because we process each edge once.
Space Complexity: O(n) due to the storage of the parent and rank arrays.
1public class UnionFind {
2 private int[] root;
3 private int[] rank;
4 public UnionFind(int size) {
5 root = new int[size];
6 rank = new int[size];
7 for (int i = 0; i < size; i++) {
8 root[i] = i;
9 rank[i] = 1;
10 }
11 }
12 public int Find(int x) {
13 if (root[x] != x) {
14 root[x] = Find(root[x]);
15 }
16 return root[x];
17 }
18 public bool Union(int x, int y) {
19 int rootX = Find(x);
20 int rootY = Find(y);
21 if (rootX != rootY) {
22 if (rank[rootX] > rank[rootY]) {
23 root[rootY] = rootX;
24 } else if (rank[rootX] < rank[rootY]) {
25 root[rootX] = rootY;
26 } else {
27 root[rootY] = rootX;
28 rank[rootX]++;
29 }
30 return true;
31 }
32 return false;
33 }
34}
35
36public class Solution {
37 public int[] FindRedundantConnection(int[][] edges) {
38 int n = edges.Length;
39 UnionFind uf = new UnionFind(n + 1);
40 foreach (int[] edge in edges) {
41 if (!uf.Union(edge[0], edge[1])) {
42 return edge;
43 }
44 }
45 return new int[0];
46 }
47}In C#, the solution structure follows the Union-Find approach established in previous solutions. Edges are processed through union checks, with the combination of union and find functions identifying the redundant connection inducing a cycle.
The DFS approach involves simulating the construction of the graph and utilizing DFS to detect cycles whenever a new edge is being added. If a cycle is detected upon adjacent traversal, that edge is the redundant one.
Time Complexity: O(n^2), potentially examining each pair of nodes connected by added edges in the worst case.
Space Complexity: O(n), dictated by recursive stack depth in the DFS and the graph representation.
1
This Java implementation operates through graph nodes maintained in a map of sets, iterating through edges with DFS evaluations on the fly to identify loops promptly, correlating those to redundant connections.