Disjoint set with path compression, C++


  • 0
    Y

    disjoint set is designed to solve union-find problem.
    It is very fast when applied with path compression.

    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int N = M.size();
            if (N == 0)
                return 0;
                
            d.resize(N);
            for (int i = 0; i < N; ++i)
                d[i] = i;
                
            for (int i = 0; i < N; ++i)
                for (int j = i+1; j < N; ++j)
                    if (M[i][j] == 1)
                        merge(i, j);
            
            int count = 0;
            for (int i = 0; i < N; ++i)
                if (i == d[i])
                    count ++;
            return count;
        }
        
        
        void merge(int i, int j)
        {
            d[parent(i)] = parent(j);
        }
        
        int parent(int x)
        {
            if (d[x] == x)
                return x;
            return d[x] = parent(d[x]); // path compression
        }
        
        vector<int> d;  // disjoint set
    };
    

  • 0
    D

    Hi, your code is simple and easy to understand! except this line

    return d[x] = parent(d[x]); // path compression
    

    Could you help to explain? Thanks!


  • 2
    Y

    @Datochi
    find the topmost parent, and assign it to all the descendants in the path, so that the path is shorter(compressed).

    before:
    1->2
    2->2
    3->1
    4->3
    5->4
    2 is the topmost parent.

    after parent(5) called:
    1->2
    2->2
    3->2
    4->2
    5->2
    now all descendants in the path point to 2


Log in to reply
 

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