DSU

PHOTO EMBED

Sat Jun 19 2021 06:06:18 GMT+0000 (UTC)

Saved by @Randumkeng

class Solution {
    int ans ;
public:
    
    int find(int u,vector<int>& parent)
    {
        if(u == parent[u])
            return u;

        else
            return parent[u] = find(parent[u],parent);
    }

    void combine (int u, int v,vector<int>& size,vector<int>& parent)
    {
        u = find(u,parent);
        v = find(v,parent);

        if(u == v)
            return;

        else
        {
            ans--;
            if(size[u] > size[v])
            {
                parent[v] = u;
                size[u] += size[v];
            }

            else
            {
                parent[u] = v;
                size[v] += size[u];
            }

        }
    }
    
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> parent(n+1,0);
        vector<int> size(n+1,1);
        size[0]=0;
        for(int i=1;i<=n;i++)
            parent[i]=i;
        ans =n;
        for(int i=0;i<n;i++)
            for(int j=0;j<isConnected[0].size();j++)
            {
                if(i!=j&&isConnected[i][j]==1)
                {
                    combine(i+1,j+1,size,parent);
                }
            }
        
        return ans;
    }
};
content_copyCOPY

disjoint set union with path compression and union by size

https://leetcode.com/problems/number-of-provinces/submissions/