有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c
    直接相连，那么城市 a 与城市 c 间接相连。
    省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
    给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相
    连，而 isConnected[i][j] = 0 表示二者不直接相连。
    返回矩阵中 省份 的数量。
    亲戚问题、朋友圈问题

    解法一：深度优先
    获取一个城市，通过递归找到离该城市最远的城市，标记为已访问，然后逐个向内进行标记

    1. public int findCircleNum(int[][] isConnected) {
    2.     int provinces = isConnected.length;
    3.     boolean[] visited = new boolean[provinces];
    4.     int circles = 0;
    6.     for (int i = 0; i < provinces; i++) {
    7.         if (!visited[i]) {
    8.             dfs(isConnected, visited, provinces, i);
    9.             circles++;
    10.         }
    11.     }
    13.     return circles;
    14. }
    16. public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
    17.     for (int j = 0; j < provinces; j++) {
    18.         if ((isConnected[i][j] == 1) && !visited[j]) {
    19.             visited[j] = true;
    20.             dfs(isConnected, visited, provinces, j);
    21.         }
    22.     }
    23. }

    解法二：广度优先
    获取一个城市，先标记与该城市直连的城市(最近的)，然后逐步向外扩散寻找

    1. public int bfs(int[][] isConnected) {
    2.     int provinces = isConnected.length;
    3.     boolean[] visited = new boolean[provinces];
    4.     int circles = 0;
    5.     Queue<Integer> queue = new LinkedList<Integer>();
    7.     for (int i = 0; i < provinces; i++) {
    8.         if (!visited[i]) {
    9.             queue.offer(i);
    11.             while (!queue.isEmpty()) {
    12.                 int j = queue.poll();
    13.                 visited[j] = true;
    15.                 for (int k = 0; k < provinces; k++) {
    16.                     if ((isConnected[j][k] == 1) && !visited[k]) {
    17.                         queue.offer(k);
    18.                     }
    19.                 }
    20.             }
    22.             circles++;
    23.         }
    24.     }
    26.     return circles;
    27. }

    解法三：并查集
    将每个城市看成一个节点，如果两个城市相连，则建立树关系，选出其中一个为head，
    如果两个树中的节点也相连，则将其中一个head设置为另一个树的head
    两个方法 ：一个寻找head节点，一个合并树

    1. static int mergeFind(int[][] isConnected) {
    2.     int provinces = isConnected.length;
    3.     int[] head = new int[provinces];
    4.     int[] level = new int[provinces];
    6.     for (int i = 0; i < provinces; i++) {
    7.         head[i] = i;
    8.         level[i] = 1;
    9.     }
    11.     for (int i = 0; i < provinces; i++) {
    12.         for (int j = i + 1; j < provinces; j++) {
    13.             if (isConnected[i][j] == 1) {
    14.                 merge(i, j, head, level);
    15.             }
    16.         }
    17.     }
    19.     int count = 0;
    21.     //找出所有的head 
    22.     for (int i = 0; i < provinces; i++) {
    23.         if (head[i] == i) {
    24.             count++;
    25.         }
    26.     }
    28.     return count;
    29. }
    31. //查找head节点
    32. static int find(int x, int[] arr) {
    33.     if (arr[x] == x) {
    34.         return x;
    35.     }
    37.     elsearr[x] = find(arr[x], arr);
    39.     //路径压缩，每一个节点直接能找到head 
    40.     return arr[x];
    41. }
    43. static void merge(int x, int y, int[] arr, int[] level) {
    44.     int i = find(x, arr);
    45.     int j = find(y, arr);
    47.     //深度比较短的树的head往深度大的树上挂，使合并后的深度尽量小 
    48.     if (i == j) {
    49.         return;
    50.     }
    52.     if (level[i] <= level[j]) {
    53.         arr[i] = j;
    54.     } else {
    55.         arr[j] = i;
    56.     }
    58.     //深度加1 
    59.     level[j]++;
    60. }