C++ union find concise solution


  • 0
    J
    class Solution {
    public:
        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
            int len = edges.size();
            vector<int> root(len+1, -1);
            vector<int> ans;
            for(int i=1; i<=len; i++)
            {
                root[i] = i;
            }
            
            for(auto edge : edges)
            {
                int f = edge[0];
                int s = edge[1];
                while(root[f] != f)
                    f = root[f];
                while(root[s] != s)
                    s = root[s];
                if(f == s)
                    ans = edge;
                root[f] = s;
            }
            
            return ans;
        }
    };
    

Log in to reply
 

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