QUESTION:

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: [[1,1,0], [1,1,0], [0,0,1]] 输出: 2 说明：已知学生0和学生1互为朋友，他们在一个朋友圈。 第2个学生自己在一个朋友圈。所以返回2。 示例 2:

输入: [[1,1,0], [1,1,1], [0,1,1]] 输出: 1 说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。 注意：

N 在[1,200]的范围内。 对于所有学生，有M[i][i] = 1。 如果有M[i][j] = 1，则有M[j][i] = 1。

EXPLANATION:

leetcode上的题很多都是直接面对数字的题目，直接解决算法问题而和实际现实生活中的问题链接不上，而头条的算法之前一个特点就是很少设置边界限制，需要你自己去考虑边界设置，第二个特点就是现在看到的特点，就是需要你自己去考虑一个实际问题，然后再抽象成算法问题，可能是想考察一下问题的抽象能力吧。
思路：可以采用dfs的方法，将所有同学轮询一遍，将轮询到的标记上，这样就能够得到圈子总数了。
步骤：
1.创建一个boolean数组visted来标记该同学是否被轮询到了
2.从第0个同学开始轮询，当该同学没有在任何朋友圈中，也就是visted[i]=false的时候，需要查看他的朋友圈
3.将他的朋友圈进行dfs的轮询，也就是如果他是j的朋友，那么就将M[j]同学的所有朋友圈进行轮询
4.这样就可以将第i个同学的朋友圈算出来，因为已经用了visted进行标记，所以未标记到的就不在这个朋友圈
5.在同学遍历结束后，就可以获取到共有多少个朋友圈

SOLUTION:

class Solution {
    public int findCircleNum(int[][] M) {
        boolean[] visted = new boolean[M.length];
        int result = 0;
        for(int i = 0;i<M.length;i++){
            if(visted[i]) continue;
            visted[i] = true;
            findCircleNumHelper(M,i,visted);
            result++;
        }
        return result;
    }
    
    public void findCircleNumHelper(int[][] M ,int i,boolean[] visted){
        for(int j = 0;j<M[i].length;j++){
            if(M[i][j]==0 || visted[j])continue;
            visted[j] = true;
            findCircleNumHelper(M,j,visted);
        }
    }
}