DFS 04

深度优先搜索

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length; // 城市总数
        boolean[] isVisited = new boolean[n];   // 初始化boolean就为false
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!isVisited[i]) {
                dfs(isConnected, n, i, isVisited);
                res++;
            }
        }
        return res;
    }

    public static void dfs(int[][] isConnected, int n, int curTown, boolean[] isVisited) {
        for (int j = 0; j < n; j++) {
            if (isConnected[curTown][j] == 1 && !isVisited[j]) {
                isVisited[j] = true;
                dfs(isConnected, n, j, isVisited);
            }
        }
    }
}