割点(关节点)

What · 是什么

割点(articulation point / cut vertex)是删除后使无向图极大连通分量数增加的点。朴素做法是枚举每个点删除后跑一遍DFS判连通性，复杂度O(V(V+E))。Tarjan算法在DFS过程中维护dfn(DFS序)和low(不经过父边能到达的最小dfn)，在O(V+E)内一次DFS求出所有割点。判定条件：对于非根节点u，若存在子节点v使得low[v]>=dfn[u]，则u是割点；对于根节点，若在DFS生成树中有两个及以上子节点，则根是割点。该算法是割点/桥/双连通分量/圆方树等系列结构的基础。

Why · 为什么

How · 实现

伪代码

tarjan(u, parent):
  dfn[u] = low[u] = ++timer
  child_count = 0
  for v in adj[u]:
    if not visited[v]:
      child_count += 1
      tarjan(v, u)
      low[u] = min(low[u], low[v])
      if parent != root and low[v] >= dfn[u]:
        is_cut[u] = True
      # 根节点判断在循环外: if parent==root and child_count>=2: is_cut[u]=True
    elif v != parent:
      low[u] = min(low[u], dfn[v])

Python 实现

import sys

sys.setrecursionlimit(1 << 25)


def find_cut_vertices(n, adj):
    """求无向图所有割点。
    adj[u] = [v, ...], 顶点编号 0..n-1
    return: 割点集合(升序list)
    """
    dfn = [0] * n
    low = [0] * n
    is_cut = [False] * n
    timer = [0]

    def dfs(u, parent):
        dfn[u] = low[u] = timer[0] = timer[0] + 1
        child = 0
        for v in adj[u]:
            if not dfn[v]:
                child += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= dfn[u]:
                    is_cut[u] = True
            elif v != parent:
                low[u] = min(low[u], dfn[v])
        if parent == -1 and child >= 2:
            is_cut[u] = True

    for s in range(n):
        if not dfn[s]:
            dfs(s, -1)
    return [i for i in range(n) if is_cut[i]]


if __name__ == "__main__":
    # 测试1: OI Wiki示例, 割点为2
    # 0-1-2-3, 2-4, 2-5, 4-6(环), 5-6  => 割点应为 {1, 2}
    adj = [[] for _ in range(7)]
    edges = [(0, 1), (1, 2), (2, 3), (2, 4), (2, 5), (4, 6), (5, 6)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    assert find_cut_vertices(7, adj) == [1, 2], find_cut_vertices(7, adj)

    # 测试2: 单个环, 无割点
    adj2 = [[] for _ in range(4)]
    for u, v in [(0, 1), (1, 2), (2, 3), (3, 0)]:
        adj2[u].append(v)
        adj2[v].append(u)
    assert find_cut_vertices(4, adj2) == [], find_cut_vertices(4, adj2)

    # 测试3: 简单链 0-1-2, 1为割点
    adj3 = [[] for _ in range(3)]
    for u, v in [(0, 1), (1, 2)]:
        adj3[u].append(v)
        adj3[v].append(u)
    assert find_cut_vertices(3, adj3) == [1], find_cut_vertices(3, adj3)

    # 测试4: 根节点为割点: 星形 0-1,0-2,0-3, 0为根且多子树
    adj4 = [[] for _ in range(4)]
    for v in (1, 2, 3):
        adj4[0].append(v)
        adj4[v].append(0)
    assert find_cut_vertices(4, adj4) == [0], find_cut_vertices(4, adj4)

    print("cut-vertex: ALL TESTS PASSED")

易错点

• 根节点割点判定条件不同：必须有>=2个DFS子树才算割点，单子树根删除不增加分量
• 返祖边更新low时用dfn[v]而非low[v]，且必须跳过父节点(无重边时)以免误判
• Python递归默认栈深~1000，需setrecursionlimit，大图考虑迭代栈
• 无向图建边要双向add，漏了会导致图不完整误判

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/cut/
• CP-Algorithms✓ https://cp-algorithms.com/graph/cutpoints.html
• 书籍✓ CPH ch17 pp167-172