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.
1class UnionFind {
2 private int[] root;
3 private int[] rank;
4
5 public UnionFind(int size) {
6 root = new int[size];
7 rank = new int[size];
8 for (int i = 0; i < size; ++i) {
9 root[i] = i;
10 rank[i] = 1;
11 }
12 }
13
14 public int find(int x) {
15 if (root[x] != x) {
16 root[x] = find(root[x]);
17 }
18 return root[x];
19 }
20
21 public boolean union(int x, int y) {
22 int rootX = find(x);
23 int rootY = find(y);
24 if (rootX != rootY) {
25 if (rank[rootX] > rank[rootY]) {
26 root[rootY] = rootX;
27 } else if (rank[rootX] < rank[rootY]) {
28 root[rootX] = rootY;
29 } else {
30 root[rootY] = rootX;
31 rank[rootX]++;
32 }
33 return true;
34 }
35 return false;
36 }
37}
38
39public class Solution {
40 public int[] findRedundantConnection(int[][] edges) {
41 int n = edges.length;
42 UnionFind uf = new UnionFind(n + 1);
43 for (int[] edge : edges) {
44 if (!uf.union(edge[0], edge[1])) {
45 return edge;
46 }
47 }
48 return new int[0];
49 }
50}This Java solution implements the Union-Find structure with methods to find and union elements. The findRedundantConnection method iterates through edges, returning the first non-unionable edge as the result.
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.
1The JavaScript solution uses an adjacency list structure and conducts DFS on a subset of vertices. Pre-checks for edge redundancy locate its provenance if cycles signify extraneous articulation.