题目链接
    image.png

    1. class Solution {
    2.     // 1.我的，深度优先
    3.     public int findCircleNum1(int[][] arr) {
    4.         boolean[] bool = new boolean[arr.length];
    5.         // 保存省份
    6.         int count = 0;
    7.         for(int i = 0; i < arr.length; i++) {
    8.             // 查询与1相连或者间接连接的城市
    9.             if(bool[i]) continue;
    11.             count++;
    12.             // 当前城市被使用
    13.             bool[i] = true;
    14.             // 将其所关联的进行标识
    15.             for(int j = 0; j < arr.length; j++) {
    16.                 if(i != j && arr[i][j] == 1) {
    17.                     bool[j] = true;
    18.                     logo(j, bool, arr);
    19.                 }
    20.             }
    21.         }
    22.         return count;
    23.     }
    25.     /**
    26.      *  标识关联的点
    27.      */
    28.     public void logo(int index, boolean[] bool, int[][] arr) {
    29.         for(int i = 0; i < bool.length; i++) {
    30.             if(i != index) {
    31.                 if(!bool[i] && arr[index][i] == 1) { // 有关联
    32.                     bool[i] = true;
    33.                     // 这里也需要间接查询标识
    34.                     logo(i, bool, arr);
    35.                 }
    36.             }
    37.         }
    38.     }
    40.     // 2.老师的深度优先
    41.     public int findCircleNum(int[][] arr) { 
    42.         int citys = arr.length;
    44.         boolean[] visited = new boolean[citys];
    45.         int provinces = 0; // 计数器
    46.         for(int i = 0; i < citys; i++) {
    47.             if(!visited[i]) { // 深度优先
    48.                 dfs(i, citys, visited, arr);
    49.                 provinces++;
    50.             }
    51.         }
    52.         return provinces;
    53.     }
    55.     public void dfs(int i, int citys, boolean[] visited, int[][] arr) {
    56.         for(int j = 0; j < citys; j++) {
    57.             if(arr[i][j] == 1 && !visited[j]) {
    58.                 visited[j] = true;
    59.                 dfs(j, citys, visited, arr);
    60.             }
    61.         }
    62.     }
    63. }