朋友圈

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

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

示例 1：

1
2
3
4
5
6
7
输入：
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出：2 
解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回 2 。

示例 2：

1
2
3
4
5
6
输入：
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出：1
解释：已知学生 0 和学生 1 互为朋友，学生 1 和学生 2 互为朋友，所以学生 0 和学生 2 也是朋友，所以他们三个在一个朋友圈，返回 1 。

提示：

  • 1 <= N <= 200
  • M[i][i] == 1
  • M[i][j] == M[j][i]

代码：

51%52

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int findCircleNum(int[][] M) {
        if(M==null||M.length==0)return 0;
        int num=M.length;
        int[] fri=new int[num];
        int mark=0;
        for(int i=0;i<num;i++)
        {
            if(fri[i]==0)
            {
                //如果还没遍历过，则开始寻找同伴
                mark++;
                //这是一个队列，用于广度遍历
                ArrayList<Integer> ls=new ArrayList<>();
                int count=1;
                ls.add(i);
                for(int j=0;j<count;j++)
                {
                    int index=ls.get(j);
                    for(int k=0;k<num;k++)
                    {
                        if(fri[k]==0&&M[index][k]==1)
                        {
                            fri[k]=mark;
                            count++;
                            ls.add(k);
                        }
                    }
                }
            }
            else
                continue;
        }
        return mark;
    }
}