找出图中规模最大的连通子图代码
时间: 2024-05-14 10:19:02 浏览: 21
下面是一个使用并查集实现的找出图中规模最大的连通子图的代码:
```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):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.size[px] < self.size[py]:
px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
def get_sizes(self):
return [self.size[self.find(x)] for x in range(len(self.parent))]
def largest_connected_component(edges):
n = max(max(e) for e in edges) + 1
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
sizes = uf.get_sizes()
return max(sizes)
```
其中 `edges` 是一个包含所有边的列表,每条边用两个节点表示。函数 `largest_connected_component` 返回图中规模最大的连通子图的大小。