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 def __init__(self, size):
3 self.parent = list(range(size))
4 self.rank = [1] * size
5
6 def find(self, x):
7 if self.parent[x] != x:
8 self.parent[x] = self.find(self.parent[x])
9 return self.parent[x]
10
11 def union(self, x, y):
12 rootX = self.find(x)
13 rootY = self.find(y)
14 if rootX != rootY:
15 if self.rank[rootX] > self.rank[rootY]:
16 self.parent[rootY] = rootX
17 elif self.rank[rootX] < self.rank[rootY]:
18 self.parent[rootX] = rootY
19 else:
20 self.parent[rootY] = rootX
21 self.rank[rootX] += 1
22 return True
23 return False
24
25class Solution:
26 def findRedundantDirectedConnection(self, edges):
27 n = len(edges)
28 parent = list(range(n + 1))
29 can1 = can2 = None
30
31 for u, v in edges:
32 if parent[v] != v:
33 can1 = [parent[v], v]
34 can2 = [u, v]
35 v = 0
36 else:
37 parent[v] = u
38
39 uf = UnionFind(n + 1)
40
41 for u, v in edges:
42 if v == 0: continue
43 if not uf.union(u, v):
44 return can1 if can1 else [u, v]
45
46 return can2
47The Python code uses the Union-Find construct to handle multiple paths effectively and determines early if redundant connections are present or removal is optimal, readying to designate that action among potentially overlapping connectivity options.
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 private void Dfs(int[] parent, bool[] visited, ref bool hasCycle, int node) {
if (hasCycle) return;
visited[node] = true;
if (parent[node] != 0) {
int next = parent[node];
if (!visited[next]) {
Dfs(parent, visited, ref hasCycle, next);
} else {
hasCycle = true;
}
}
visited[node] = false;
}
public int[] FindRedundantDirectedConnection(int[][] edges) {
int n = edges.Length;
int[] parent = new int[n + 1];
Array.Fill(parent, 0);
int[] can1 = null, can2 = null;
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (parent[v] != 0) {
can1 = new int[] { parent[v], v };
can2 = new int[] { u, v };
edge[1] = 0;
} else {
parent[v] = u;
}
}
bool hasCycle = false;
for (int i = 1; i <= n; i++) {
if (hasCycle) break;
var visited = new bool[n + 1];
Dfs(parent, visited, ref hasCycle, i);
}
return hasCycle ? can1 : can2;
}
}
The C# build dynamically maneuvers through edges and constructs transparency in potential cycle generation while managing excessive connections through refined DFS calls, conclusively identifying the cycle or alternate participant edge.