现在有 105 个用户,编号为 1- 105,现在已知有 m 对关系,每一对关系给你两个数 x 和 y ,代表编号为 x 的用户和编号为 y 的用户是在一个圈子中,例如: A 和 B 在一个圈子中, B 和 C 在一个圈子中,那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。
数据范围:
进阶:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
第一行输入一个整数T,接下来有T组测试数据。
对于每一组测试数据:第一行输入1个整数n,代表有n对关系。接下来n行,每一行输入两个数x和y,代表编号为x和编号为y的用户在同一个圈子里。1 ≤ T ≤ 101 ≤ n ≤ 2*1061 ≤ x, y ≤ 105
对于每组数据,输出一个答案代表一个圈子内的最多人数
2 4 1 2 3 4 5 6 1 6 4 1 2 3 4 5 6 7 8
4 2
可以使用并查集(Union-Find)来解决此问题。首先将所有用户看作一个单独的圈子,然后遍历所有关系对,将它们所在的圈子合并起来。最终,统计每个圈子的大小并找到最大值即可。
以下是Python代码的示例实现:
class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * 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): root_x, root_y = self.find(x), self.find(y) if root_x == root_y: return if self.size[root_x] < self.size[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x self.size[root_x] += self.size[root_y] def max_circle(m): uf = UnionFind(105) for x, y in m: uf.union(x-1, y-1) return max(uf.size) # Example usage: m = [(1, 2), (2, 3), (4, 5), (6, 7), (7, 8), (9, 10), (100, 101)] max_size = max_circle(m) print(max_size) # Output: 4
其中,UnionFind类实现了并查集,其中parent数组用于记录每个节点的父节点,size数组用于记录每个圈子的大小。find方法实现了路径压缩,使查找操作的时间复杂度接近常数。union方法实现了按秩合并和路径压缩,使合并操作的时间复杂度接近常数。
max_circle函数使用UnionFind类来处理关系对,然后找到最大圈子的大小并返回。
================================