C++ easy Union-Find solution


  • 0
    M
        unordered_map<int, int> pre;
        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
            vector<int> res;
            for(int i=0;i<edges.size();i++) {
                pre[edges[i][0]]=edges[i][0];
                pre[edges[i][1]]=edges[i][1];
            }
            for(int i=0;i<edges.size();i++) {
                int a=find(edges[i][0]), b=find(edges[i][1]);
                if(a!=b) pre[a]=b;
                else res=edges[i];
            }
            return res;
        }
        
        int find(int x) {
            while(pre[x]!=x) x=pre[x];
            return x;
        }

Log in to reply
 

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