[684. Redundant Connection] C++_Union Find


  • 0
    class Solution {
    public:
    int find(int node, unordered_map<int,int>& mp){
        while(mp[node] != node){
            node = mp[node];
        }
        return node;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> res;
        unordered_map<int, int> mp;//child-parent
        for(int i = 0; i < edges.size(); ++i){
            vector<int> tmp = {min(edges[i][0], edges[i][1]), max(edges[i][0], edges[i][1])};
            int new_add = 1;
            if(mp.find(tmp[0]) == mp.end()){
                mp[tmp[0]] = tmp[0];
            }
            if(mp.find(tmp[1]) == mp.end()){
                mp[tmp[1]] = find(tmp[0], mp);
                new_add = 0;
            }
            if(new_add){
                int p0 = find(tmp[0], mp);
                int p1 = find(tmp[1], mp);
                if(p0 == p1){
                    res = edges[i];
                }else{
                    mp[p0] = min(p0, p1);
                    mp[p1] = min(p0, p1);
                }
            }
        }
        return res;
    }
    };

Log in to reply
 

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