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 def __init__(self, size):
3 self.root = list(range(size))
4 self.rank = [1] * size
5
6 def find(self, x):
7 if x != self.root[x]:
8 self.root[x] = self.find(self.root[x])
9 return self.root[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.root[rootY] = rootX
17 elif self.rank[rootX] < self.rank[rootY]:
18 self.root[rootX] = rootY
19 else:
20 self.root[rootY] = rootX
21 self.rank[rootX] += 1
22 return True
23 return False
24
25class Solution:
26 def findRedundantConnection(self, edges):
27 uf = UnionFind(len(edges) + 1) # nodes are 1-indexed
28 for u, v in edges:
29 if not uf.union(u, v):
30 return [u, v]This solution implements a Union-Find class with path compression and rank optimization to efficiently find and union nodes. By iteratively applying union operation on each edge, it detects the first edge causing a cycle, which is the redundant edge to be returned.
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.
1using System;
using System.Collections.Generic;
public class Solution {
private bool dfs(Dictionary<int, HashSet<int>> graph, int source, int target, HashSet<int> visited) {
if (source == target) return true;
visited.Add(source);
foreach (var neighbor in graph[source]) {
if (!visited.Contains(neighbor)) {
if (dfs(graph, neighbor, target, visited)) return true;
}
}
return false;
}
public int[] FindRedundantConnection(int[][] edges) {
var graph = new Dictionary<int, HashSet<int>>();
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
if (!graph.ContainsKey(u)) graph[u] = new HashSet<int>();
if (!graph.ContainsKey(v)) graph[v] = new HashSet<int>();
if (graph[u].Contains(v) || (graph[v].Contains(u) && dfs(graph, u, v, new HashSet<int>()))) {
return edge;
}
graph[u].Add(v);
graph[v].Add(u);
}
return new int[0];
}
}The C# approach translates an adjacency list graph for DFS applicability, scanning each edge to probe possible path existence, marking feasible redundant connections upon cycle detection through recursion.