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 <stdio.h>
2#include <stdlib.h>
3
4typedef struct {
5 int *root;
6 int *rank;
7} UnionFind;
8
9UnionFind* createUnionFind(int size) {
10 UnionFind *uf = (UnionFind *)malloc(sizeof(UnionFind));
11 uf->root = (int *)malloc(size * sizeof(int));
12 uf->rank = (int *)malloc(size * sizeof(int));
13 for (int i = 0; i < size; ++i) {
14 uf->root[i] = i;
15 uf->rank[i] = 1;
16 }
17 return uf;
18}
19
20int find(UnionFind *uf, int x) {
21 if (uf->root[x] != x) {
22 uf->root[x] = find(uf, uf->root[x]);
23 }
24 return uf->root[x];
25}
26
27int unionSets(UnionFind *uf, int x, int y) {
28 int rootX = find(uf, x);
29 int rootY = find(uf, y);
30 if (rootX != rootY) {
31 if (uf->rank[rootX] > uf->rank[rootY]) {
32 uf->root[rootY] = rootX;
33 } else if (uf->rank[rootX] < uf->rank[rootY]) {
34 uf->root[rootX] = rootY;
35 } else {
36 uf->root[rootY] = rootX;
37 uf->rank[rootX]++;
38 }
39 return 1;
40 }
41 return 0;
42}
43
44int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
45 UnionFind *uf = createUnionFind(edgesSize + 1);
46 int* redundantEdge = (int*)malloc(2 * sizeof(int));
47 for (int i = 0; i < edgesSize; i++) {
48 if (!unionSets(uf, edges[i][0], edges[i][1])) {
49 redundantEdge[0] = edges[i][0];
50 redundantEdge[1] = edges[i][1];
51 *returnSize = 2;
52 return redundantEdge;
53 }
54 }
55 *returnSize = 0;
56 return NULL;
57}This C solution applies a similar Union-Find algorithm. It allocates memory for the root and rank arrays and implements the same logic through find and unionSets functions, efficiently detecting the redundant edge via 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.