Union-find, 3ms beats 93.60%


  • 0
    H
    int find(vector<int> &p, int x) {
        while(p[x] != -1) {
            x = p[x];
        }
        return x;
    }
    
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> p(1001,-1);
        int x,y;
        for( auto e:edges) {
            x = find(p, e[0]);            
            y = find(p, e[1]);
            
            if(x == y) {
                return e;
            } else
                p[x] = y;
        }
        return vector<int>(2,0);
    }

Log in to reply
 

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