好友关系的连通分量数目

547. Friend Circles (Medium)

Input:
[[1,1,0],
 [1,1,0],
 [0,0,1]]

Output: 2

Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

题目描述：

  好友关系可以看成是一个无向图，例如第 0 个人与第 1 个人是好友，那么 M[0] [1]和 M[1] [0] 的值都为 1。

代码：

public int findCircleNum(int [][]M){
    if(M==null||M.length==0)
        return 0;
    int n=M.length;
    boolean visited[]=new boolean[n]; //表示是否已经查看某人的朋友关系。
    int res=0;
    for(int i=0;i<n;i++){
        if(!visited[i]){ //该人没有被查看过
            dfs(M,i,visited);
            res++;
        }
    }
    return res;
}
public void dfs(int [][]M,int i,boolean[]vistited){
    visited[i]=true; //表示已经访问过该人的朋友关系
    for(int k=0;k<M.length;k++){
        if(M[i][k]==1&&!visited[k]){//判断哪个人和i是朋友，然后再去检查该人的朋友关系。
            dfs(M,k,visited);
        }
    }
}