547. Friend Circles

Link

Solution

根據每個人去做DFS檢查關係，把直接朋友的人跟間接朋友的人標記成已經處理過。並在所有直接、間接朋友都處理完之後將朋友圈數+1。

直到所有人都已經檢查過。

    public int findCircleNum(int[][] M) {
        int N = M.length;
        int[] checked = new int[N];
        int count = 0;
        for(int i = 0; i < N; i++){
            if(checked[i] != 1){
                dfs(M, checked, i);
                count++;
            }
        }
        return count;
    }
    
    public void dfs(int[][] M, int[] checked, int i){
        checked[i] = 1;
        for(int j = 0; j < M.length; j++){
            if(checked[j] == 0 && M[i][j] == 1){
                dfs(M, checked, j);
            }
        }
    }