# 684 Redundant Connection

In this problem, a tree is anundirectedgraph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of`edges`. Each element of`edges`is a pair`[u, v]`with`u < v`, that represents anundirectededge connecting nodes`u`and`v`.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge`[u, v]`should be in the same format, with`u < v`.
Example 1:
Input:
[[1,2], [1,3], [2,3]]
Output:
[2,3]
Explanation:
The given undirected graph will be like this:
1
/ \
2 - 3
Example 2:
Input:
[[1,2], [2,3], [3,4], [1,4], [1,5]]
Output:
[1,4]
Explanation:
The given undirected graph will be like this:
5 - 1 - 2
| |
4 - 3
Note:
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
The Idea: This is a disjoint set problem, which is essentially used for the purpose of identifying a cycle in an undirected graph. What we do is continuously perform a union on each `(i,j)` if both `i` and `j` are already not in the same union. If they are, they are the cause of the cycle.
Complexity: O(n) (bounded by Inverse Ackermann)
struct Node {
Node(const int id) : id(id), parent(this), depth(0) {};
int depth;
const int id;
Node *parent;
};
class DisjointSet {
public:
DisjointSet(const int ids) : num_ids(ids) {
init_find.reserve(ids);
for (int i = 1; i <= ids; i++)
make_set(i);
}
int find(const int x) {
if (init_find.find(x) == init_find.end()) return -1;
else return _find(x);
}
void union_(const int x, const int y) {
int x_parent = find(x);
int y_parent = find(y);
if (init_find[y_parent]->depth <= init_find[x_parent]->depth)
init_find[y_parent]->parent = init_find[x_parent]->parent;
else if (init_find[y_parent]->depth > init_find[x_parent]->depth)
init_find[x_parent]->parent = init_find[y_parent]->parent;
if (init_find[y_parent]->depth == init_find[x_parent]->depth)
init_find[x_parent]->depth++;
}
private:
const size_t num_ids;
void make_set(const int x) {
if (init_find.find(x) != init_find.end()) return;
else init_find.insert({ x, new Node(x) });
}
int _find(const int x) {
Node *iter = init_find[x]->parent;
if (iter->id == iter->parent->id) {
return iter->id;
}
else {
// path compression
while (iter->id != iter->parent->id)
iter = iter->parent;
init_find[x]->parent = init_find[iter->id];
return iter->id;
}
}
unordered_map<int, Node*> init_find;
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
DisjointSet ds(edges.size());
for (vector<int> &v : edges) {
int a_find = ds.find(v);
int b_find = ds.find(v);
if (a_find == b_find) {
return v;
}
else {
ds.union_(v, v);
}
}
}
};