547. Number of Provinces

Union Find

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n)
    {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
        }
    }

    int find(int x)
    {
        if (x != parent[x])
        {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionNodes(int n1, int n2)
    {
        int p1 = find(n1);
        int p2 = find(n2);

        if (p1 == p2) return;

        if (rank[p1] > rank[p2])
        {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        }
        else
        {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected)
    {
        int n = isConnected.size();
        UnionFind uf(n);

        int cnt = n;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (isConnected[i][j] && uf.find(i) != uf.find(j))
                {
                    cnt--;
                    uf.unionNodes(i, j);
                }
            }
        }
        return cnt;
    }
};

• T: $O(N^2)$
• S: $O(N)$