求最大连通分量代码python

这里提供一个使用DFS（深度优先搜索）算法求解无向图最大连通分量的代码示例（Python实现）：

from collections import defaultdict

def dfs(u, vis, G):
    """
    DFS遍历连通分量
    """
    vis[u] = True
    cnt = 1 # 连通分量顶点数
    for v in G[u]:
        if not vis[v]:
            cnt += dfs(v, vis, G)
    return cnt

def max_component(n, edges):
    """
    求最大连通分量
    """
    G = defaultdict(list) # 邻接表表示无向图
    for u, v in edges:
        G[u].append(v)
        G[v].append(u) # 无向图需要加两条边

    vis = [False] * (n + 1)
    ans = 0 # 最大连通分量的顶点数
    for i in range(1, n + 1):
        if not vis[i]:
            cnt = dfs(i, vis, G)
            ans = max(ans, cnt)
    return ans

if __name__ == '__main__':
    n, m = map(int, input().split()) # 读入顶点数和边数
    edges = [list(map(int, input().split())) for _ in range(m)] # 读入所有边
    print(max_component(n, edges)) # 输出最大连通分量的顶点数

该算法的时间复杂度为 $O(n+m)$，其中 $n$ 是顶点数，$m$ 是边数。