Time Cost

15min1s

Implementation

None

Code

• Solution

  class Solution {
  public:
    vector<int> parent;
    vector<int> rank;
  
    int find(int i) {
        if (parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }
  
    void join(int i, int j) {
        int rootI = find(i), rootJ = find(j);
        if (rootI > rootJ) parent[rootJ] = rootI;
        else if (rootI < rootJ) parent[rootI] = rootJ;
        else {
            parent[rootJ] = rootI;
            rank[rootI]++;
        }
    }
  
    int findCircleNum(vector<vector<int>>& isConnected) {
          
        parent.resize(isConnected.size());
        rank.resize(isConnected.size(), 0);
        for (int i=0; i<isConnected.size(); i++) parent[i] = i;
  
        int result = isConnected.size();
        for (int i=0; i<isConnected.size(); i++) {
            for (int j=i+1; j<isConnected.size(); j++) {
                if (!isConnected[i][j]) continue;
                if (find(i) == find(j)) continue;
                join(i, j);
                result--;
            }
        }
        return result;
    }
  };