Sponsored
Sponsored
This approach uses a Union-Find (Disjoint Set Union, DSU) structure to detect cycles and check for nodes with two parents. The goal is to handle two situations: a node having two parents, and a cycle existing in the graph. We iterate through the edges to identify a node with two parents and mark the offending edge. Then, we use the Union-Find structure to track cycles and find the redundant connection based on the identified edges.
Time Complexity: O(n), where n is the number of edges.
Space Complexity: O(n), for storing the parent and rank arrays.
1class UnionFind {
2 private int[] parent;
3 private int[] rank;
4
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
14 public int find(int x) {
15 if (parent[x] != x) {
16 parent[x] = find(parent[x]);
17 }
18 return parent[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) return false;
25 if (rank[rootX] > rank[rootY]) {
26 parent[rootY] = rootX;
27 } else if (rank[rootX] < rank[rootY]) {
28 parent[rootX] = rootY;
29 } else {
30 parent[rootY] = rootX;
31 rank[rootX]++;
32 }
33 return true;
34 }
35}
36
37public class Solution {
38 public int[] findRedundantDirectedConnection(int[][] edges) {
39 int n = edges.length;
40 int[] parent = new int[n + 1];
41 for (int i = 1; i <= n; i++) {
42 parent[i] = i;
43 }
44
45 int[] can1 = null;
46 int[] can2 = null;
47 for (int[] edge : edges) {
48 int u = edge[0], v = edge[1];
49 if (parent[v] != v) {
50 can1 = new int[] {parent[v], v};
51 can2 = new int[] {u, v};
52 edge[1] = 0;
53 } else {
54 parent[v] = u;
55 }
56 }
57
58 UnionFind uf = new UnionFind(n + 1);
59 for (int[] edge : edges) {
60 if (edge[1] == 0) continue;
61 int u = edge[0], v = edge[1];
62 if (!uf.union(u, v)) return can1 == null ? edge : can1;
63 }
64 return can2;
65 }
66}
67The Java implementation maps nodes with potential redundant edges and explores which connection among candidates could feasibly be removed to preserve tree properties while applying Union-Find for cycle detection, ensuring correct upstream connections converge towards a union of sets strategy.
In this method, we focus on identifying two scenarios: an edge creating a cycle in the graph and a node with two parents. With graph traversal, primarily cross-check with parent pointers and DFS for cycle confirmation, fine-tuning insights to pinpoint a last array occurrence redundant connection.
Time Complexity: O(n^2) with recursive verification.
Space Complexity: O(n), memoizing visited nodes.
1
Java smoothly navigates through the DFS calling structure, ensuring it captures cyclic constructs effectively. With ordered parent review and composite result tones through graph narrative construction, cycles are masterfully exposed.