class Solution {
public:
    vector<int> idx, sz;
    int root(int x) {
        while(x != idx[x]) {
            idx[x] = idx[idx[x]];
            x = idx[x];
        }
        return x;
    }
    void join(int a, int b) {
        int root_a = root(a);
        int root_b = root(b);
        if(root_a != root_b) {
            if(sz[root_a] > sz[root_b]) {
                idx[root_b] = idx[root_a];
                sz[root_a] += sz[root_b];
            }
            else {
                idx[root_a] = idx[root_b];
                sz[root_b] += sz[root_a];
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = (int) isConnected.size();
        idx.resize(n);
        sz.resize(n);

        for(int i = 0; i < n; i++) {
            sz[i] = 1;
            idx[i] = i;
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(isConnected[i][j] == 1) {
                    join(i, j);
                }
            }
        }
        set<int> st;
        for(int i = 0; i < n; i++) {
            st.insert(root(i));
        }
        return (int) st.size();

    }
};