图论——割点与割边

GJX_Algorithm · 2024-11-02 10:57:19 · 算法·理论

割点与割边

割点

前置知识

• 建议先学强连通分量，学会 dfn 数组与 low 数组后再来学习割点。

• 点双连通：在无向图中，删除一个点（不是 x 或者 y）后，点 x 和点 y 仍然能够彼此到达，那么称 x 和 y 是点双连通的。

• 边双连通：在无向图中，删除一条边后，点 x 和点 y 仍然能够彼此到达，那么称 x 和 y 是边双连通的。

• 点双连通不具有传递性（如图），边双连通具有传递性。

割点的定义，结论，与判定

• 定义：在无向图 G 中，若删除 cur 后，连通块的数量增加，则 cur 称为无向图 G 的一个割点（割顶）。

• 结论：至少有 3 个点的无向图，才可能存在割点。

• 判定：

  1. 若搜索树中，有从 cur 到 nxt 的连边，当 low_{nxt} \ge dfn_{cur} 时，说明 nxt 能到达的最小时间戳在 cur 的时间戳之上，nxt 被 cur 与 cur 之前的结点“隔开”，cur 可能是割点。

  2. 对于所有可能的割点，只要 cur 不是搜索树的根结点，或者 cur 是根结点，但是 cur 的子结点大于 1 个，那么 cur 就是割点。

核心代码

void tarjan(int cur)
{
    int cnt = 0; //用来统计cur有几个子结点
    low[cur] = dfn[cur] = ++tot; //打上时间戳
    for (int nxt : nbr[cur])
    {
        if (dfn[nxt] == 0) //nxt还没去过
        {
            tarjan(nxt); //递归继续搜索
            low[cur] = min(low[cur], low[nxt]); //维护cur能到达的最小时间戳low[cur]
            if (low[nxt] >= dfn[cur]) 
            {
                cnt++; //nxt还没去过，说明nxt是cur在当前搜索树中的一个子结点
                if (cur != root || cnt >= 2) //排除根结点且只有一个子结点的情况
                  ans[cur] = 1;
            }
        }
        else low[cur] = min(low[cur], dfn[nxt]); //nxt已经去过了，所以nxt还没有回溯，不能用low[nxt]
    }
    return ;
}

例题与练习

• P3388（模板）

• UVA10199（模板）

• CF1761E

割边

割边的定义、性质与判定

• 割边的定义：在无向图中，若删除一条边 e 后，连通块的数量增加，那么称边 e 为这张无向图的一条割边。

• 割边的性质：

  1. 割边一定不在环上，在环上的一定不是割边。

  2. 割边涉及的通常是“必经边”问题。

  3. 若删除一条割边，则联通块数量加一。

• 割边的判定：

  1. 同样先维护出 dfn 值与 low 值。

  2. 如图，若 low_{nxt} > dfn_{cur}，则边 cur \to nxt 为割边。

核心代码

void edge_add(int u, int v)
{
    a[++cnt1] = {u, v};
    return ;
}
void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++tot;
    for (int i = head[u]; ~i; i = nxt[i])
    {
        int v = to[i];
        if (dfn[v] == 0)
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) edge_add(u, v);
        }
        else if (v != fa) low[u] = min(low[u], dfn[v]);
    }
    return ;
}

例题与练习

• T103481

• P1656

• P7687