/*

    思路就是遍历所有人，对于每一个人，寻找他的好友，找到好友后再找这个好友的好友

    ，这样深度优先遍历下去，设置一个flag记录是否已经遍历了这个人。

    其实dfs真正有用的是flag这个变量，因为如果m个人最多m个朋友圈，设置后flag后，相同的朋友圈会

    检测到flag就会不算数。

     */

    public int findCircleNum(int[][] M) {

        int m = M.length;

        if (m==0) return 0;

        int res = 0;

        boolean[] flag = new boolean[m];

        for (int i = 0; i < m; i++) {

            if (dfs(i,M,flag)>0)

                res++;

        }

        return res;

    }

    public int dfs(int i,int[][] M,boolean[] flag){

        if (flag[i]) return 0;

        flag[i] = true;

        int count = 1;

        for (int j = 0; j < M.length; j++) {

            if (i!=j&&M[i][j]==1)

                count+=dfs(j,M,flag);

        }

        return count;

    }