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 ofedges. Each element ofedgesis a pair[u, v]withu < v, that represents anundirectededge connecting nodesuandv.
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, withu < v.
Example 1:
[[1,2], [1,3], [2,3]]
The given undirected graph will be like this:
/ \
2 - 3
Example 2:
[[1,2], [2,3], [3,4], [1,4], [1,5]]
The given undirected graph will be like this:
5 - 1 - 2
| |
4 - 3
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 {
DisjointSet(const int ids) : num_ids(ids) {
for (int i = 1; i <= ids; 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)
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 {
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
DisjointSet ds(edges.size());
for (vector<int> &v : edges) {
int a_find = ds.find(v[0]);
int b_find = ds.find(v[1]);
if (a_find == b_find) {
return v;
else {
ds.union_(v[0], v[1]);