547. 朋友圈

image.png

解题思路

用的主要方法是广度优先遍历，利用一个队列
其实就是个广度优先遍历来找图中有几个连通分量
一旦队列为空，就代表这是一个连通分量

代码

class Solution {
    
    public int findCircleNum(int[][] M) {
    int count=0;
    int l=M.length;
    int [] visited=new int[l];
    Queue<Integer> q=new LinkedList<Integer>();
    for(int i=0;i<l;i++){
       if(visited[i]==0){
           q.add(i);
       
       while(!q.isEmpty()){
           int s=q.poll();
           visited[s]=1;
           for(int j=0;j<l;j++){
               if(visited[j]==0&&M[s][j]==1){//来判断是否与其他点有联系
                   q.add(j);
               }
           }
       }
       
       count++;//一旦queue为空，就代表一个连通分量的结束
       }
    }
return count;
    }
   
}