Tarjan

发表于 分类于 本文字数： 2000 阅读时长 ≈ 5 分钟

以Tarjan命名的算法有很多，这里主要讲用来求连通分量的那几个。

有向图求强连通分量

强联通分量（Strongly Connected Component），简称SCC。

首先解释一下什么是强连通分量。

强连通分量

强连通分量的定义就是，在同一个强连通分量里面的两个点必定能够互相到达。
最简单的强连通分量就是一个环，环上的任意两个点都可以互相到达，满足强连通分量的要求。

强连通分量的一个重要的性质就是，给定一个简单无向图，将其上面的所有强连通分量缩成点之后可以得到一张DAG（有向无环图）。

思路

这个思路主要是基于上面的那个性质，也就是强连通分量缩点之后可以得到一张DAG。
而在一张DAG上，你是不可以走回头路的，这也是DAG可以做DP的一大原因。
所以，我们把这张图DFS一遍，给每一个节点一个DFS序的编号，我们对于每一个强连通分量一定能找到一个类似于其根节点的地方，满足其DFS序是其能访问到的所有节点的DFS序中最小的那一个。
那我们如果想要找到这样的“根节点”，可以记录下来每一个节点的DFS序和其能访问到的所有节点的DFS序的最小值，并称之为“回溯值”，并判断两者是否相等。
那我们就对这张图做一遍DFS，记录下每一个点的DFS序和回溯值，如果回溯完了之后一看发现两者相等，那就意味着当前我们访问到的这一茬节点是在同一个SCC里面的。

示例代码

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
int dfn[N], low[N], cnt;//DFS序以及回溯值
bool vis[N];
int scc[N], sz[N], sc;//所属的强连通分量的编号，强连通分量的大小
int sta[N], tt;
void tarjan(int p)
{
    dfn[p] = low[p] = ++cnt;
    sta[++tt] = p;
    for(int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[p] = min(low[p], low[j]);
        }
        else if(vis[j])
        {
            low[p] = min(low[p], dfn[j]);
        }
    }
    if(dfn[p] == low[p])
    {
        sc++;
        while(sta[tt] != p)
        {
            scc[sta[tt]] = sc;
            sz[sc]++;
            vis[sta[tt]] = false;
            tt--;
        }
        scc[sta[tt]] = sc;
        sz[sc]++;
        vis[sta[tt]] = false;
        tt--;
    }
}

无向图求边双连通分量

边双联通分量（Edge-Double Connected Component），简称EDCC。

介绍边双连通分量之前，需要先介绍一下割边。

割边与边双

一条边是割边的判定标准是，去掉该边之后会使原先连通的两部分不连通。
而边双连通分量的判定标准则是，在同一个边双连通分量中的任意两个点，都有两条不同的路径可以到达对方。
这两条路径只要求经过的边集不同，点集可以一样。或者也可以认为是两点之间存在一条路径不经过割边。
最简单的边双是一个环，任意一对点都可以有顺时针和逆时针两条不同的路径连接，符合边双的定义。

边双比较常用的一个性质就是，将一张连通图中的所有边双缩成点，可以得到一棵树。

思路

与之前的思路类似，我们仍然是记录每一个节点的DFS序和回溯值，只不过这一次的回溯值记录的是当前节点不经过其父亲能到达的节点的DFS序的最小值。
我们可以发现，如果一条边 $(u,v)$ 是割边，且 $dfn_u < dfn_v$（即 $u$ 是 $v$ 的父亲），那么点 $v$ 只能通过边 $(u,v)$ 到达点 $v$。
通过这个性质，我们可以推出当 $(u,v)$ 是割边且 $dfn_u < dfn_v$ 时，$dfn_u < low_v$。
同时，我们还可以推出来这个 $v$ 的 $low_v$ 是等于 $dfn_v$ 的，这和之前我们找SCC时用的根节点的套路差不多。
如果实在不放心，可以通过再进行一遍DFS来维护EDCC，只需要忽略掉所有的割边就可以将整张图分割成一系列的EDCC了。

标记割边的时候，可以通过将边从0开始编号，这样可以通过异或操作来快速找到一对反向边。

示例代码

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
int isBridge[M];
int dfn[N], low[N], cnt;
int sta[N], tt;
int scc[N], sc, sz[N];
void tarjan(int p, int fa)
{
    low[p] = dfn[p] = ++cnt;
    sta[++tt] = p;
    for(int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j, i);
            low[p] = min(low[p], low[j]);
            if(dfn[p] < low[j])
                isBridge[i] = isBridge[i ^ 1] = true;
        }
        else if(j != fa)
        {
            low[p] = min(low[p], dfn[j]);
        }
    }
    if(dfn[p] == low[p])
    {
        ++sc;
        while(sta[tt] != p)
        {
            scc[sta[tt]] = sc;
            sz[sc]++;
            tt--;
        }
        scc[sta[tt]] = sc;
        sz[sc]++;
        tt--;
    }
}

点双连通分量

点双连通分量（Vertice-Double Connected Component），简称VDCC。

同样，介绍点双连通分量之前需要先介绍一下割点。

割点与点双

一个点是割点的判定标准是，去掉该点之后会使原先联通的两部分不连通。
而点双连通分量的判定标准则是，在同一个点双连通分量内的任意两个点都有两条不同的路径相互连接。
其中这两条路径的点集和边集都必须不一样，不过不可以认为是两点之间存在一条路径不经过割点。
最简单的点双是一条边+两个端点，不过这个只是极端情况，更常见一点的是一个环。

割点与点双的关系不像割边与边双的关系，边双里面没有割边，但是点双里面可以有一个或多个割点。
同时，割点也不一定必须要在点双里面，比如说两个点双之间只以一条链连接，这条链上的所有点都是割点，却不在任何点双里面。

思路

我们仍然套用之前的套路，记录下来每一个点的DFS序和回溯值，而回溯值仍然是不经过其父亲节点能够到达的所有节点的DFS序的最小值。
假如说当前点 $u$ 是个割点，其一定会有一个儿子 $v$，满足 $dfn_u \leq low_v$，也就是说 $v$ 除了通过 $u$ 之外是无法访问到其祖先节点的。
有一个特例是我们DFS生成树的根节点，或者说是我们搜索的起始点。根节点没有祖先，也就无法通过上面的方法判断了。
不过还是可以补救的：我们考虑根节点的度数。
如果根节点只有一棵子树，那么把根节点删掉之后不会影响其余节点的连通性；否则其所有子树之间就不会再连通，根节点也就成了割点。

判定点双的话还是套用之前比对DFS序和回溯值的方法，如果当前节点的DFS序与其回溯值相等，那就意味着其不经过父节点可以访问到的节点中没有一个可以访问到其祖先，这些点也就与其在同一个VDCC之中。

示例代码

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
int isCut[M];
int dfn[N], low[N], cnt;
int sta[N], tt;
int scc[N], sc, sz[N];
int deg[N];
void tarjan(int p, int fa)
{
    low[p] = dfn[p] = ++cnt;
    sta[++tt] = p;
    for(int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        deg[p]++;
        if(!dfn[j])
        {
            tarjan(j, i);
            low[p] = min(low[p], low[j]);
            if(dfn[p] <= low[j])isCut[p] = true;
        }
        else if(j != fa)
        {
            low[p] = min(low[p], dfn[j]);
        }
    }
    if(dfn[p] == low[p])
    {
        ++sc;
        while(sta[tt] != p)
        {
            scc[sta[tt]] = sc;
            sz[sc]++;
            tt--;
        }
        scc[sta[tt]] = sc;
        sz[sc]++;
        tt--;
    }
}

这份代码只负责了一般情况下的割点判断，根节点的话需要在枚举的时候特殊处理一下。