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.
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.
1#include <vector>
2#include <unordered_set>
3#include <unordered_map>
4using namespace std;
5
6bool dfs(int source, int target, unordered_map<int, unordered_set<int>>& graph, unordered_set<int>& visited) {
7 if (source == target) return true;
8 visited.insert(source);
9 for (int neighbor : graph[source]) {
10 if (!visited.count(neighbor)) {
11 if (dfs(neighbor, target, graph, visited)) return true;
12 }
13 }
14 return false;
15}
16
17class Solution {
18public:
19 vector<int> findRedundantConnection(vector<vector<int>>& edges) {
20 unordered_map<int, unordered_set<int>> graph;
21 for (auto& edge : edges) {
22 int u = edge[0], v = edge[1];
23 unordered_set<int> visited;
24 if (graph.count(u) && graph.count(v) && dfs(u, v, graph, visited)) {
25 return edge;
26 }
27 graph[u].insert(v);
28 graph[v].insert(u);
29 }
30 return {};
31 }
32};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.