Tarjan-割边问题

前言

之前介绍Tarjan算法求强连通分量时，提到了代码段中对于访问过的邻接点应用其时间戳来更新追溯值，不是说用追溯值更新会导致答案错误，而是为了和后续双连通分量的代码保持统一。学习双连通分量求解，要先了解割点和割边的概念，本文来介绍割边。

关于Tarjan算法求解强连通分量，见：SCC-Tarjan算法，强连通分量算法，从dfs到Tarjan详解-CSDN博客

---

割边定义

在一个无向图中，如果将一条边删除后连通分量会被断开分为 2 个及以上，这个点就是一个割边（也称桥）。

割边的求解

割边的定义十分简洁，其求解思路也十分简单，同样是基于Tarjan-SCC算法（详见）。

割边判定定理

• 对于节点x，如果其搜索树上子节点y，满足low[y] > dfn[x]，则边<x，y>就是一条割边。

我们通过下面例子来理解一下该判定定理。

如上图我们的边(1,2)而言，有low[2] > dfn[1]，故(1,2)是一条割边，而割断(1,2)后确实得到了两个强连通分量

但是像(2,3),(3,4),(2,4)由于都不满足low[y] > dfn[x]，所以不是割边，而割断它们任意一条也都没有令强连通分量数目增加。

证明（非严谨）

low[y] > dfn[x]，说明从y出发，在不经过（x，y）这条边的前提下，不存在路径使得y访问到x或者比x还早节点。说明x在环外，（x，y）是环与环外一点相连的边，故割断后可增加强连通分量数。
反之，若low[y] <= dfn[x]，则说明y能绕行其他边到达x或者比x更早的节点，说明x也在环内，（x，y）是环内的边，割断后不会令强连通分量数目增加。

算法实现

数据结构

我们判定定理中low[y] > dfn[x]的含义为不经过(x , y)的情况下是不能够通过其他边访问x或者比x更早节点的，也就是说我们通过(x,y)访问y时，不能通过边(y,x)来更新y的追溯值，这就要求我们以一种能够记录边编号的数据结构存图。我们可以使用邻接表或者链式前向星来存图，这里我们使用链式前向星。

关于链式前向星详见：一种实用的边的存储结构–链式前向星-CSDN博客

#define N 151
#define M 10010
struct edge
{
    int v, nxt;
} edges[M];
int head[N]{0}, idx = 0;
void addedge(int u, int v)
{
    edges[idx] = {v, head[u]};
    head[u] = idx++;
}

算法流程

• 对x深搜，打时间戳，抵达x的上一条边编号为pre
• 通过编号为j的边(x,y)访问子节点y
• y未访问，则对y深搜，更新low[x]
  • 如果low[y] >low[x]，则（x，y）为割边
• y已访问，如果j不是pre的反向边，则更新low[x] = min(low[x], dfn[y])

代码详解

int dfn[N]{0}, low[N]{0}, tot = 0, cnt = 0, root; // tot访问节点的时间戳编号
// dfn 时间戳 low节点所能访问的最小时间戳 tot数目
vector<pair<int, int>> cut;

void tarjan(int x, int pre)
{
    dfn[x] = low[x] = ++tot;
    int y;
    for (int j = head[x]; ~j; j = edges[j].nxt)
    {
        y = edges[j].v;
        if (!dfn[y])
        {
            tarjan(y, j);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x])
            {
                cut.emplace_back(x, y);
            }
        }
        else if (j != (pre ^ 1)) // 不是反边
        {
            low[x] = min(low[x], dfn[y]);
        }
    }
}

OJ练习

P1656 炸铁路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)