Simple C++ UnionFind with explanation


  • 0

    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];
        }
    };
    

  • 0

    @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.
    Status: Wrong Answer
    Submitted: 7 minutes ago

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

    Output: [3,2]

    Expected: [2,3]


  • 0

    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;
        }
    };
    

Log in to reply
 

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