Amazon Graph：连通分量有多少个，孤立节点算不算？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练无向图，n个节点0..n-1包含孤立点；自环和重复边不增加连接。
• 有向弱连通可忽略方向，强连通必须SCC，不用DSU替代。

解题路线

1. DSU初始每点一个分量，result=n。每边find两个根，不同才按size合并并result--；同根边只形成冗余连接。
2. 不变量：每DSU集合恰是已处理边形成的一个分量。跨集合边连接恰两个分量而减少1，集合内边不改变数量，因此最终正确。
3. 必须从完整顶点集合初始化；只从edges抽节点会漏无边的孤立点，空边n=5应返回5。
4. 图已经给邻接列表时DFS数起点也O(V+E)，DSU适合持续只加边。若允许删除边，不能直接把result加1，删除桥和非桥影响不同。

手动走一遍

训练n=5,edges=[(0,1),(1,2),(2,0),(3,3),(0,1)]，分量{0,1,2},{3},{4}，结果3；自环/重复不减计数。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def component_count(n,edges):
    """Undirected graph numbered 0..n-1, isolated vertices included."""
    if n < 0:raise ValueError("negative vertex count")
    parent=list(range(n))
    size=[1]*n
    def find(v):
        while parent[v]!=v:
            parent[v]=parent[parent[v]]
            v=parent[v]
        return v
    result=n
    for a,b in edges:
        if not (0<=a<n and 0<=b<n):raise ValueError("invalid vertex")
        a,b=find(a),find(b)
        if a==b:continue
        if size[a]<size[b]:a,b=b,a
        parent[b]=a
        size[a]+=size[b]
        result-=1
    return result

复杂度

O((n+e)·α(n))近摊还时间、O(n)空间；DFS替代O(n+e)，题面约束决定选择。

易错点与追问

容易失分的边界

• 只收集边中节点。
• 每边都result--。
• DSU计算有向强连通。

继续深挖

• 在线边增量查询怎么做？
• 删边为何需要别的数据结构？
• 还要各分量大小如何返回？