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.
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 x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public bool Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX == rootY) return false;
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
public class Solution {
public int[] FindRedundantDirectedConnection(int[][] edges) {
int n = edges.Length;
int[] parent = new int[n + 1];
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
int[] can1 = null;
int[] can2 = null;
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (parent[v] != v) {
can1 = new int[] { parent[v], v };
can2 = new int[] { u, v };
edge[1] = 0;
} else {
parent[v] = u;
}
}
UnionFind uf = new UnionFind(n + 1);
foreach (var edge in edges) {
if (edge[1] == 0) continue;
int u = edge[0], v = edge[1];
if (!uf.Union(u, v)) return can1 ?? edge;
}
return can2;
}
}
C# establishes a Union-Find setup that efficiently integrates union logic to manage parentage and sibling-set connectivity, with checks ensuring processed edges reconcile multiple parent situations while identifying cycles.
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.
1class Solution:
2 def findRedundantDirectedConnection(self, edges):
3 def dfs(parent, visited, cycle, node):
4 if cycle[0]:
5 return
6 visited[node] = True
7 next = parent[node]
8 if next != 0:
9 if not visited[next]:
10 dfs(parent, visited, cycle, next)
11 else:
12 cycle[0] = True
13 visited[node] = False
14
15 n = len(edges)
16 parent = [0] * (n + 1)
17
18 can1, can2 = None, None
19 for u, v in edges:
20 if parent[v] != 0:
21 can1 = (parent[v], v)
22 can2 = (u, v)
23 v = 0
24 else:
25 parent[v] = u
26
27 cycle = [False]
28 for i in range(1, n + 1):
29 if cycle[0]:
30 break
31 visited = [False] * (n + 1)
32 dfs(parent, visited, cycle, i)
33
34 return can1 if cycle[0] else can2
35The Python script leverages DFS walkthrough simplification to evaluate node links and rank suitable output arrays. Using inner loops partnered with recursive cycle validation, it correctly adjudicates offending connections.