# Simple C++ UnionFind with explanation

• Start with a completely disjoint set of unique trees which are represented within a vector where each index originally corresponds to a unique tree root ( a tree consisting of only one node, itself, the root ). Tree is uniquely identified with an integer value between 1 and 2000 inclusive ( the 0th index is NOT used ).

``````        const int size=2001;
vector<int> res{}, tree(size);
for (int i=0; i<size; ++i){ tree[i]=i; }
``````

We update this vector of trees to form new trees whenever an edge connects a parent with a child. We process each edge, one at a time. For each edge representing a parent/child relationship, set all the tree index values to the current child's edge value if the tree index value was equal to the current parent's edge value . This coalesces the parent/child into a new tree whose unique value is the value of the last child added onto this tree. Once the tree values of a parent/child edge are the same, then we know a loop has been encountered, since the tree points back to itself.

``````        for (auto& edge : edges){
int p=edge[0], q=edge[1];
int parent=tree[p], child=tree[q];
if (parent==child) { return vector<int>{p,q}; }
for (int i=0; i<size; ++i){ if (tree[i]==parent) { tree[i]=child; } }
}

``````

Example: let's take a step-by-step look at the following input to see how the output was formulated:

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: Original tree will be like this:

``````  1
/ \
2 - 3
``````

For this tree, we are only interested in the vector elements at index 1, 2, and 3, since those indexes are used to uniquely identify 3 separate trees which will be incrementally joined together as the edges are processed.

``````Before processing [[1,2], [1,3], [2,3]]:

index: 0123
value: 0123

trees:

1

2   3

``````

There are originally 3 separate trees: [ 1, 2, 3 ]. ( Note: we do NOT use index 0, so the value of index 0 always remains as 0 )

``````After processing the first edge [1,2]:

index: 0123
value: 0223

trees:

2
/
2   3
``````

There are now 2 separate trees: [ 2, 3 ]. Tree 2 contains two nodes now that there is an edge between the tree node at index 1 and the tree node at index 2. Tree 3 remains unchanged, and still contains one node ( itself ).

``````After processing the second edge [1,3]:

index: 0123
value: 0333

tree:

3
/ \
3   3
``````

There is now 1 tree: [ 3 ]. Tree 3 contains three nodes now that there is an edge between the tree node at index 1 and the tree node at index 3.

``````After processing the third edge [2,3]:

index: 0123
value: 0333

tree:

3
/ \
3 - 3

``````

There would be a cycle created if we add this edge. We know this because the tree value (3) at index 2 representing the edge's parent (2) is equal to the tree value (3) at index 3 representing the edge's child (3) ( i.e. 3==3 ). Therefore, this edge, [ 2, 3 ] is returned as the output of this function.

``````class Solution{
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges){
const int size=2001;
vector<int> res{}, tree(size);
for (int i=0; i<size; ++i){ tree[i]=i; }
for (auto& edge : edges){
int p=edge[0], q=edge[1];
int parent=tree[p], child=tree[q];
if (parent==child) { return vector<int>{p,q}; }
for (int i=0; i<size; ++i){ if (tree[i]==parent) { tree[i]=child; } }
}
return res;
}
};
``````

After reading https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Find, I discovered a simple way to update the parent tree's values with the child tree's value when the parent/child are joined. This is done during the `_find` operation. If there was a modification to either the parent or child node of the edge being processed ( i.e. `tree[i] != i` ), then update `tree[i]` value to the same value of the child tree node whom was joined into this tree last.

``````class Solution{
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges){
const int size=2001;
vector<int> res{}, tree(size);
for (int i=0; i<size; ++i){ tree[i]=i; }
for (auto& edge : edges){
int p=_find(tree,edge[0]),q=_find(tree,edge[1]);
if (p==q) { return edge; }
tree[p]=q;
}
return res;
}

private:
int _find(vector<int>& tree, int i){
if (tree[i]!=i){
tree[i]=_find(tree,tree[i]);
}
return tree[i];
}
};
``````

• @administrators I think there is a problem with test case #7. For the following input, there is no output, since there is no loop from `[ 1 -> 2 -> 3 -> 4 ]`. I was able to pass all TCs a day or two ago... my solution's output for the following input is an empty vector...

7 / 38 test cases passed.
Submitted: 7 minutes ago

Input: [[3,4],[2,3],[1,2]]

Output: [3,2]

Expected: [2,3]

• A more traditional union-find code structure...

``````class Solution{
public:
vector<int> parent{};
void Union(int a, int b){
int target=parent[a];
for (int i=0; i<parent.size(); ++i)
if (parent[i]==target)
parent[i]=b;
}

int Find(int x){
if (parent[x]==x)
return x;
parent[x]=Find(parent[x]);
return parent[x];
}

vector<int> findRedundantConnection(vector<vector<int>>& edges){
vector<int> res{};
parent.resize(edges.size()+1);
for (int i=0; i<parent.size(); ++i)
parent[i]=i;
for (auto &&edge: edges){
int m=edge[0], n=edge[1];
m=Find(m);
n=Find(n);
if (m==n)
res=edge;
else
Union(m,n);
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.