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.
1#include <vector>
2#include <numeric>
3using namespace std;
4
5class UnionFind {
6 vector<int> root, rank;
7public:
8 UnionFind(int size) : root(size), rank(size, 1) {
9 iota(root.begin(), root.end(), 0);
10 }
11 int find(int x) {
12 if(root[x] != x) {
13 root[x] = find(root[x]);
14 }
15 return root[x];
16 }
17 bool unionSets(int x, int y) {
18 int rootX = find(x);
19 int rootY = find(y);
20 if(rootX != rootY) {
21 if(rank[rootX] > rank[rootY]) {
22 root[rootY] = rootX;
23 } else if(rank[rootX] < rank[rootY]) {
24 root[rootX] = rootY;
25 } else {
26 root[rootY] = rootX;
27 rank[rootX]++;
28 }
29 return true;
30 }
31 return false;
32 }
33};
34
35class Solution {
36public:
37 vector<int> findRedundantConnection(vector<vector<int>>& edges) {
38 int n = edges.size();
39 UnionFind uf(n + 1);
40 for(auto& edge : edges) {
41 if(!uf.unionSets(edge[0], edge[1])) {
42 return edge;
43 }
44 }
45 return {};
46 }
47};The C++ solution uses a similar approach with the UnionFind class. Each edge is checked using the unionSets method. If unionSets returns false, it indicates a cycle, and thus the edge is redundant.
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
This solution constructs the graph incrementally while running DFS to check for paths from vertex u to vertex v before adding each edge. If the path exists, addition of the edge creates a cycle, thereby identifying it as redundant.