Union find part 2

684. Redundant Connection

https://leetcode.com/problems/redundant-connection/

C++ with rank optimization

class UnionFind {
    vector<int> uf, ranks_;
    public:
    UnionFind(int n) {
        ranks_ = vector<int>(n + 1, 0);        
        uf = vector<int>(n + 1, 0);                
        for (int i = 0; i < uf.size(); ++i)uf[i] = i;
    }
    bool union_(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        // Meger low rank tree into high rank tree
        if (ranks_[py] < uf[px])
            uf[py] = px;           
        else if (ranks_[px] < ranks_[py])
            uf[px] = py;
        else {
            uf[py] = px;
            ranks_[px] += 1;
        }  
        return true;
    }
    int find(int x) {        
        if (x != uf[x])
            uf[x] = find(uf[x]);        
        return uf[x];
    }
};
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionFind s(edges.size());
        for(auto &edge:edges){
            if(!s.union_(edge[0],edge[1]))return edge;
        }
        return {};   
    }
};

runtime 8ms

Concise the logic with rank consideration.

class UnionFind {
    vector<int> ranks_, uf;
    public:
    UnionFind(int n) {
        ranks_ = vector<int>(n + 1, 0);  
        for(int i=0;i<n+1;++i)uf.push_back(i);
    }
    void uni(int x, int y) {
        int px = find(x), py = find(y);
        if (ranks_[py] < ranks_[px]) uf[py] = px;           
        else if (ranks_[px] < ranks_[py]) uf[px] = py;
        else {
            uf[py] = px;
            ranks_[px] += 1;
        }  
    }
    int find(int x) {        
        if (x != uf[x]) uf[x] = find(uf[x]);        
        return uf[x];
    }
};
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionFind s(edges.size());
        for(auto &edge:edges){
            
            if(s.find(edge[0])==s.find(edge[1]))return edge;
            else s.uni(edge[0], edge[1]);
        }
        return {};   
    }
};

C++ without rank optimization

class UnionFind {
    vector<int> ranks_, uf;
    public:
    UnionFind(int n) {
        for(int i=0;i<n+1;++i)uf.push_back(i);
    }
    void uni(int x, int y) {
        uf[find(y)] = find(x);
    }
    int find(int x) {        
        if (x != uf[x]) uf[x] = find(uf[x]);        
        return uf[x];
    }
};
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionFind s(edges.size());
        for(auto &edge:edges){  
            if(s.find(edge[0])==s.find(edge[1]))return edge;
            else s.uni(edge[0], edge[1]);
        }
        return {};   
    }
};

runtime is still 8 ms

Union find without a separate class

class Solution {
public:
    vector<int> uf;
    void uni(int x, int y) {uf[find(y)] = find(x);}
    int find(int x) {        
        if (x != uf[x]) uf[x] = find(uf[x]);        
        return uf[x];
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        for(int i=0;i<edges.size()+1;++i)uf.push_back(i);
        for(auto &edge:edges){  
            if(find(edge[0])==find(edge[1]))return edge;
            else uni(edge[0], edge[1]);
        }
        return {};   
    }
};