C++ Union-Find solution, using weighted union-fast algorithm


  • 0
    B

    Built a tree for each connection unit.
    Use uf to record node i's parent node and its weight(size of the tree).

    class Solution
    {
    public:
    int findCircleNum(vector<vector<int>>& M)
    {

        int n = M.size();
        if(!n) return 0;
        
        //Union find
        for(int i = 0; i < n; ++i) uf.push_back({i, 1});
        
        for(int i = 0; i < n; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(M[i][j] == 1)
                {
                    int rj = getRoot(j), ri = getRoot(i);
                    if(uf[rj].second < uf[ri].second) 
                    {
                        uf[rj].first = ri;
                        uf[ri].second += uf[rj].second;
                    }
                    else
                    {
                        uf[ri].first = rj;
                        uf[rj].second += uf[ri].second;
                    }
                }
            }
        }
        
        int cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            if(uf[i].first == i) cnt++; //Node i is a root.
        }
        return cnt;
    }
    private:
    int getRoot(int r)
    {
        while(uf[r].first != r) r = uf[r].first;
        return r;
    }
    vector<pair<int, int>> uf; //parent - weight
    };

Log in to reply
 

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