Tarjan算法与无向图连通性

一、无向图的割点与桥的基本概念：
   
给定无向连通图G = (V, E)
割点：
对于x∈V，从图中删去节点x以及所有与x关联的边之后，G分裂为两个或两个以上不相连的子图，则称x为割点

割边（桥）：
若对于e∈E，从图中删去边e之后，G分裂成两个不相连的子图，则称e为G的桥或割边

一般无向图（不一定连通）的割点与桥就是它的各个连通块的各点和桥

Tarjan算法基于无向图的深度优先遍历。
时间戳
在图的深度优先遍历过程中，按照每个节点第一次被访问的时间顺序，依次给予N个节点1~N的整数标记，该标记被称为“时间戳”，记为dfn[x]

搜索树
在无向连通图中任选一个节点出发进行深度优先遍历吗，每个节点只访问一次。所有发生递归的边(x, y)（换言之，从x到y是对y 的第一次访问）构成一棵树，称为“无向连通图的搜索树”。一般无向图的各个连通块的搜索树构成无向图的“搜索森林”。对于深度优先遍历出的搜索树，按照被遍历的次序，标记节点的时间戳

追溯值
追溯值low[x]。设subtree(x)表示搜索树中以x为根的子树。low[x]定义为以下节点时间戳的最小值
即：
1.subtree(x)中的节点
2.通过一条不在搜索树上的边，能够到达subtree(x)的节点

为了计算low[x]，应该先令low[x] = dfn[x],然后考虑从x出发的每条边(x, y):
若在搜索树上x是y的父节点，则令low[x] = min(low[x], low[y])
若无向边(x, y)不是搜索树上的边，则令low[x] = min(low[x], dfn[y])。

   
   
二、割边的判定法则：
无向边(x, y)是桥，当且仅当搜索树上存在x的一个子节点y，满足:

         dfn[x] < low[y]

根据定义，dfn[x] <low[y]说明从subtree(y)出发，在不经过(x, y)的前提下，不管走哪条边，都无法到达x或比x更早访问的节点。若把(x, y)删除，则subtree(y)就好像形成了封闭的环境，与节点x没有边相连，图断成了两部分，(x, y)为桥
反之，若不存在这样的子节点y，使得dfn[x] < low[y]，这说明每个subtree(y)都能绕行其他边到x或比x更早的节点,(x, y)也就不是桥

桥一定是搜索树中的边，并且一个简单环中的边一定都不是桥

   需要注意的是， 因为我们要遍历的是无向图， 所以从每个节点x出发，总能访问到他的父节点fa,根据low的计算方法，(x, fa)属于搜索树上的边，且fa不是x的子节点，故不能用fa的时间戳来更新low[x]。

   但是，如果仅记录每个节点的父节点，会无法处理重边的情况——当x与fa之间有多条边时，(x, fa)一定不是桥，在这些重复计算中，只有一条边在搜索树上，其他的几条都不算，故有重边时，dfn[fa]能用来更新low[x]

   解决方案是：记录“递归进入每个节点的边的编号”。编号可认为是边在邻接表中储存下标位置。把无向图的每条边看做双向边，成对存储在下标"2和3"，“4和5”,“6和7”…处。若沿着编号i的边递归进入节点x，则忽略从x出发的编号为i xor 1的边，通过其他边计算low[x]即可

下面的程序求出一张无向图中所有的桥。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100010;
int head[maxn],ver[maxn*2],nt[maxn*2];
int dfn[maxn],low[maxn],n,m,tot,num=0;
bool bridge[maxn*2];

void add(int x,int y)
{
   
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void tarjan(int x,int in_edge)
{
   
    dfn[x] = low[x] = ++num;
    for(int i=head[x];i;i=nt[i])
    {
   
        int y=ver[i];
        if(!dfn[y])
        {
   
            tarjan(y,i);
            low[x]=min(low[x],low[y]);

            if(low[y]>dfn[x])
                bridge[i]=bridge[i^1] =true;
        }
        else if(i != (in_edge^1))
            low[x]=min(low[x],dfn[y]);
    }
}

int main(void)
{
   
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
   
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
   
        if(!dfn[i]) tarjan(i,0);
    }

    for(int i=2;i<tot;i+=2)
        if(bridge[i]) printf("%d %d \n",ver[i^1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63