题目描述

[EN | CN]

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

给定一个 $N \times 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。

注意:

  • $N$ 在 [1,200] 的范围内。
  • 对于所有学生,有$M_{i,i} = 1$。
  • 如果有 $M_{i,j} = 1$,则有 $M_{j,i} = 1$。

解法 1:DFS

我们可以使用 DFS 来解决,对于某个学生,我们看看是否已经对他进行过 DFS:

  • 如果没有被遍历过,那么朋友圈数量 num_groups 加一,并且我们从该学生开始进行 DFS,所有路径上的学生都要标注为已被遍历过(通过 visited 数组);
  • 如果已经被遍历过,则继续。

假设学生总人数为 $n$,那么

  • 时间复杂度为 $O(n^2)$,需要遍历整个朋友圈矩阵;
  • 空间复杂度为 $O(n)$,需要用 visited 保存每个学生是否被遍历过。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        num_people = len(M)
        num_groups = 0
        visited = [False] * num_people

        def dfs(i):
            visited[i] = True
            for j in range(num_people):
                if M[i][j] and not visited[j]:
                    visited[j] = True
                    dfs(j)

        for i in range(num_people):
            if not visited[i]:
                dfs(i)
                num_groups += 1
        return num_groups
  • 执行用时:288 ms,在所有 Python3 提交中击败了 44.02% 的用户。
  • 内存消耗:14.6 MB,在所有 Python3 提交中击败了 11.11% 的用户。