解法一：并查集

  1. class Solution {
  2.     private int[] father;
  4.     public int findCircleNum(int[][] isConnected) {
  5.         final int N = isConnected.length;
  6.         father = new int[N];
  7.         for (int i = 0; i < N; ++i) {
  8.             father[i] = i;
  9.         }
  10.         for (int i = 0; i < N; ++i) {
  11.             for (int j = i + 1; j < N; ++j) {
  12.                 if (isConnected[i][j] == 1) {
  13.                     union(i, j);
  14.                 }
  15.             }
  16.         }
  17.         int ans = 0;
  18.         for (int i = 0; i < N; ++i) {
  19.             if (father[i] == i) {
  20.                 ans++;
  21.             }
  22.         }
  23.         return ans;
  24.     }
  26.     private void union(int x, int y) {
  27.         father[find(x)] = find(y);
  28.     }
  30.     private int find(int x) {
  31.         return father[x] == x ? x : find(father[x]);
  32.     }
  33. }