班上有 **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。 ``` **思路** 方法一 :DFS,遍历所有人,对于每个人寻找他的好友,然后再找他好友的好友,这样深度优先遍历下去,通过 visited 数组记录是否已经遍历完这个人,遍历到相同朋友圈, visited[i] 则标识为已经遍历过,不再次纳入朋友圈个数统计中 方法二: 并查集,将有关系的人放在一个集合中 **解法** 解法一 ```python class Solution: def findCircleNum(self, M: List[List[int]]) -> int: len_m = len(M) visited = [0 for i in range(len_m)] friend_count = 0 def dfs(M,i,visited,len_m): visited[i] = 1 for j in range(len_m): if M[i][j] == 1 and visited[j] == 0: dfs(M,j,visited,len_m) for i in range(len_m): if visited[i] == 0: friend_count += 1 dfs(M,i,visited,len_m) return friend_count ``` 解法二 ```python class Solution: def findCircleNum(self, M: List[List[int]]) -> int: len_m = len(M) self.parent = [i for i in range(len_m)] # init def find_set(i): if i == self.parent[i]: return i return find_set(self.parent[i]) def union(i,j): find_i, find_j = find_set(i),find_set(j) self.parent[find_j] = find_i for i in range(len_m): for j in range(len_m): if M[i][j]: union(i,j) return len([i for i in range(len_m) if find_set(i) == i]) ```