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 constructor(size) {
3 this.root = Array.from({ length: size }, (_, i) => i);
4 this.rank = Array(size).fill(1);
5 }
6
7 find(x) {
8 if (this.root[x] !== x) {
9 this.root[x] = this.find(this.root[x]);
10 }
11 return this.root[x];
12 }
13
14 union(x, y) {
15 let rootX = this.find(x);
16 let rootY = this.find(y);
17 if (rootX !== rootY) {
18 if (this.rank[rootX] > this.rank[rootY]) {
19 this.root[rootY] = rootX;
20 } else if (this.rank[rootX] < this.rank[rootY]) {
21 this.root[rootX] = rootY;
22 } else {
23 this.root[rootY] = rootX;
24 this.rank[rootX] += 1;
25 }
26 return true;
27 }
28 return false;
29 }
30}
31
32var findRedundantConnection = function(edges) {
33 const uf = new UnionFind(edges.length + 1);
34 for (let [u, v] of edges) {
35 if (!uf.union(u, v)) return [u, v];
36 }
37 return [];
38};The JavaScript solution mirrors the Union-Find method with adjustments for syntax in JavaScript. The findRedundantConnection function iterates over each edge and utilizes union to potentially find the redundant edge creating a cycle.
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.
1#include <unordered_set>
#include <unordered_map>
using namespace std;
bool dfs(int source, int target, unordered_map<int, unordered_set<int>>& graph, unordered_set<int>& visited) {
if (source == target) return true;
visited.insert(source);
for (int neighbor : graph[source]) {
if (!visited.count(neighbor)) {
if (dfs(neighbor, target, graph, visited)) return true;
}
}
return false;
}
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
unordered_map<int, unordered_set<int>> graph;
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
unordered_set<int> visited;
if (graph.count(u) && graph.count(v) && dfs(u, v, graph, visited)) {
return edge;
}
graph[u].insert(v);
graph[v].insert(u);
}
return {};
}
};In this C++ solution, a graph is represented via adjacency lists, utilizing sets to store edges and detect cycles using DFS. Upon discovery of a concurrent cycle path between nodes, the processing edge is flagged as redundant.