C++ union find


  • 0
    G
    class Solution {
    public:
        
        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
            unordered_map<int,int> uf;
            function<int(int)> Find = [&](int i)->int{
                if(uf.find(i) == uf.end()){
                    uf[i] = i;
                    return i;
                }
                
                if(uf[i] != i){
                    uf[i] = Find(uf[i]);
                }
    
                return uf[i];
            };
            
            function<void(int,int)> Union = [&](int i, int j){
                int r1 = Find(i);
                int r2 = Find(j);
                
                if(r1 != r2){
                    uf[r2] = r1;
                }
            };
            
            vector<int> result;
            
            for(auto &e : edges){
                if(Find(e[0]) == Find(e[1])){
                    result = e;
                    break;
                }
                
                Union(e[0],e[1]);
            }
            
            return result;
        }
    };
    

Log in to reply
 

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