图论——割点与割边

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 个点的无向图，才可能存在割点。

判定：

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

对于所有可能的割点，只要 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 为这张无向图的一条割边。

割边的性质：

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

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

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

割边的判定：

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

如图，若 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