Tarjan求割点和桥

算法 图论九讲

by szTom
under group algorithm - graph

---

前置知识

1. 邻接表存储及遍历图
2. tarjan求强连通分量

割点

割点的定义

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

也就是说，就是有个点维持着连通分量的继续，去掉那个点，这个连通分量就无法在维持下去，分成好几个连通分量。
比如说，下图中

蓝色的点就是割点。

tarjan求割点

前向边

首先，先了解什么是前向边：

将这个无向图按树排列，从子节点到其祖先的边为前向边。

即为 $low[x] < dfn[x]$ 时，有到x的前向边。

因为，low的定义是:

$$low[x]= min\{dfn[y]\ |\ (x,y) \in E\ y\not = father[x] \}$$ 即从$x$所能到达的点中$dfn[x]$最小的点。

方案

可以得出，设$y$是$x$的任意儿子，满足

$$dfn[x] \leq low[y]$$ 的点就是割点。
同时，当$x$为根节点且$x$的儿子数量多于$1$时，$x$是割点。

原理

如果一个点不是根节点，那么当它$dfn[x] \leq low[y]$时，没有关于$x$的前向边。这时删除点$x$的话，$x$的儿子节点就无法到达$x$的祖先了，故$x$是割点。
如果$x$是根节点，那么当它的儿子数量多于$1$时，删除$x$，其儿子节点无法互相到达，故$x$是割点。

代码实现

下面是P3388 【模板】割点（割顶）的代码。
其中用bool iscut[20005];来记录割点。

vector<int> G[20005]; 
int dfn[20005], low[20005];
int n, m;
int sum, root;
bool iscut[20005];
void tarjan(int x) {
    int flag = 0;
    dfn[x] = low[x] = ++sum;
    for (unsigned i = 0; i < G[x].size(); ++i) {
        int y = G[x][i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[y], low[x]);
            if (low[y] >= dfn[x]) {
                ++flag;
                if (x != root || flag > 1) iscut[x] = 1;
            }
        } else {
            low[x] = min(low[x], dfn[y]);
        }
    }
}
int main() {
    int x, y;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for ( int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            root = i;
            tarjan(i);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (iscut[i]) ++ans;
    }
    cout << ans << endl;
    for (int i = 1; i <= n; ++i) {
        if (iscut[i]) cout << i << " ";
    }
    cout << endl;
    return 0;
}

桥

定义

假设有连通图$G=\{V,E\}$，$e$是其中一条边（即$e \in E$），如果$G-e$是不连通的，则边$e$是图$G$的一条割边（桥）。

比如说，下图中，

红色箭头指向的就是割边。

tarjan求割边

和割点差不多，当存在边$(x,y) \in E$时，满足：

$$dfn[x] < low[x]$$ 时，边$(x,y)$是一条割边。

代码实现

下面代码实现了求割边，其中，当isbridge[x]为真时，$(father[x],x)$为一条割边。

int low[MAXN], dfn[MAXN], iscut[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];
void tarjan(int u, int fa) {
    father[u] = fa;
    low[u] = dfn[u] = ++dfs_clock;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) { 
                isbridge[v]=true;
                ++cnt_bridge;
            }
        } else if(dfn[v] < dfn[u] && v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

关于前向星（链式邻接表）

前向星的定义

一种数据结构，以储存边的方式来存储图。其优势有方便标记某一条边。

为什么要提前向星

本文中已经避免使用前向星，但网上绝大部分博客都使用提前向星。
下面不是前向星的教程（请自行百度），但可以帮助理解前向星。

理解前向星

1.遍历边

for (int i = head[x]; i; i = nxt[u]) {
    int y = to[i], w = weight[i];
    //code
}

相当于：

for (unsigned i = 0; i < G[x].size(); ++i) {
    int y = G[x][i].x, w = G[x][i].w;
    // code
}

2.相反边
i和i ^ 1互为反向边的编号。

邻接表要处理这种查询，可以新加一个变量记录：

struct node {
    int x, w; //original codes
    int partner;
};

在建边时，加上：

int x, y, w;
for (int i = 1; i <= m; ++i) {
    cin >> x >> y >> w;
    G[x].push_back((node) {y, w, G[y].size()});
    G[y].push_back((node) {x, w, G[x].size() - 1});
}

需要时，G[x][i]的反向边是G[G[x][i].x][G[x][i].partner]

效率问题

容易看出，前向星的空间效率的常数比邻接表大。时间复杂度上理论相等，但因为vector的常数大，时间常数比较大。

tarjan的复杂度

和模板没有区别，时间是$O(n+m)$，空间$O(n+m)$(要存图)

关于割点与桥的其他问题

定理？猜想？

可能会发现，割点与桥有如下性质:

(1) 两个割点之间的边是割边。
(2) 割边连接的点是有割点。

（1）这在很多情况上是正确无误的，但有反例，如：

（2）除了两点一边的情况，是正确的。
证明嘛：略

例题

P3388 【模板】割点（割顶）

模板题，割点。

POJ2117 Electricity

割边，不需要记录割边，tarjan时直接记录答案。
像这样：

low[u] = min(low[u],low[v]);
if (low[v] > dfn[u]) {
    ans = min(ans, G[v][i].w);
}

HDU4738 Caocao's Bridges

割点。

HDU2460 Network

割边 + LCA（暴力可以）

POJ1523 SPF

割点 + dfs。

@2019-11-21 广州市第二中学科技城校区