Tarjan-割边问题

2023-12-20 17:47:55

前言

之前介绍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)

文章来源:https://blog.csdn.net/EQUINOX1/article/details/135111150
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。