LeetCode 朋友圈题解

LeetCode 朋友圈题解题目描述班上有 N 个学生有些学生是朋友。给你一个 N x N 的矩阵 M 表示学生之间的朋友关系。如果 M[i][j] 1那么第 i 个学生和第 j 个学生彼此是朋友否则不是。求朋友圈的数量。示例输入M [[1,1,0],[1,1,0],[0,0,1]]输出2解题思路方法并查集思路使用并查集来解决这个问题。初始化并查集将每个学生作为独立的集合。遍历矩阵如果两个学生是朋友将它们合并到同一个集合。最后统计集合的数量即为朋友圈的数量。复杂度分析时间复杂度O(N^2)。空间复杂度O(N)。代码实现class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py self.find(x), self.find(y) if px py: return if self.rank[px] self.rank[py]: px, py py, px self.parent[py] px if self.rank[px] self.rank[py]: self.rank[px] 1 def find_circle_num(M): n len(M) uf UnionFind(n) for i in range(n): for j in range(i 1, n): if M[i][j] 1: uf.union(i, j) return sum(1 for i in range(n) if uf.find(i) i) # 测试 def test_find_circle_num(): M [[1, 1, 0], [1, 1, 0], [0, 0, 1]] print(find_circle_num(M)) # 输出2 if __name__ __main__: test_find_circle_num()总结朋友圈是并查集的典型应用将朋友关系合并到同一个集合最后统计集合数量。