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.
1#include <vector>
2using namespace std;
3
4class UnionFind {
5public:
6 UnionFind(int size) : parent(size), rank(size, 1) {
7 for (int i = 0; i < size; ++i) {
8 parent[i] = i;
9 }
10 }
11
12 int find(int x) {
13 if (parent[x] != x) {
14 parent[x] = find(parent[x]);
15 }
16 return parent[x];
17 }
18
19 bool unionSets(int x, int y) {
20 int rootX = find(x);
21 int rootY = find(y);
22 if (rootX == rootY) return false;
23 if (rank[rootX] > rank[rootY]) {
24 parent[rootY] = rootX;
25 } else if (rank[rootX] < rank[rootY]) {
26 parent[rootX] = rootY;
27 } else {
28 parent[rootY] = rootX;
29 rank[rootX]++;
30 }
31 return true;
32 }
33
34private:
35 vector<int> parent;
36 vector<int> rank;
37};
38
39vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
40 int n = edges.size();
41 vector<int> parent(n + 1);
42 for (int i = 1; i <= n; ++i) {
43 parent[i] = i;
44 }
45
46 vector<int> can1, can2;
47 for (const auto& edge : edges) {
48 int u = edge[0], v = edge[1];
49 if (parent[v] != v) {
50 can1 = {parent[v], v};
51 can2 = {u, v};
52 edge[1] = 0;
53 } else {
54 parent[v] = u;
55 }
56 }
57
58 UnionFind uf(n + 1);
59 for (const auto& edge : edges) {
60 if (edge[1] == 0) continue;
61 int u = edge[0], v = edge[1];
62 if (!uf.unionSets(u, v)) return can1.empty() ? edge : can1;
63 }
64 return can2;
65}
66The solution uses a Union-Find class to manage connected components and determine if nodes are already connected, which would indicate a cycle. By capturing candidates that could represent redundant connections, the solution explores potential removal strategies, resolving correctly due to its direction-following and validation process.
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.