Tarjan算法【阅读笔记】

妖狐艹你老母 2021-12-12 15:43 309阅读 0赞

应用：**线性时间**内求出**无向图的割点与桥，双连通分量。有向图的强连通分量，必经点和必经边。**

主要是求两个东西，dfn和low

**时间戳dfn：**就是dfs序，也就是每个节点在dfs遍历的过程中第一次被访问的时间顺序。

**追溯值low**：$low\[x\]$定义为$min(dfn\[subtree(x)中的节点\], dfn\[通过1条不再搜索树上的边能到达subtree(x)的节点\]）$，其中$subtree(x)$是搜索树中以$x$为根的节点。

其实这个值表示的就是这个点所在子树的最先被访问到的节点，作为这个子树的根。

**搜索树**：在无向连通图中任选一个节点出发进行深度搜索遍历，每个点只访问一次，所有发生递归的边$(x,y)$构成一棵树，称为**无向连通图的搜索树**。

## **low计算方法**： ##

先令$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\]$

这说明从$subtree(y)$出发，在不经过$(x,y)$的前提下，不管走哪条边都无法到达$x$或比$x$更早访问的节点。若把$(x,y)$删除，$subtree(y)$就形成了一个封闭的环境。

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

1 void tarjan(int x, int in_edge)
     2 {
     3     dfn[x] = low[x] = ++num;
     4     int flag = 0;
     5     for(int i = head[x]; i; i = Next[i]){
     6         int y = ver[i];
     7         if(!dfn[y]){
     8             tarjan(y);
     9             low[x] = min(low[x], low[y]);
    10             if(low[y] > dfn[x]){
    11                 bridge[i] = bridge[i ^ 1] = true;
    12             }
    13         }
    14         else if(i != (in_edge ^ 1)) 
    15             low[x] = min(low[x], dfn[y]);
    16     }
    17 }
    18 
    19 int main()
    20 {
    21     cin>>n>>m;
    22     tot = 1;
    23     for(int i = 1; i <= m; i++){
    24         int x, y;
    25         scanf("%d%d", &x, &y);
    26         if(x == y)continue;
    27         add(x, y);
    28         add(y, x);
    29     }
    30     for(int i = 1; i <= n; i++){
    31         if(!dfn[i]){
    32             tarjan(i, 0);
    33         }
    34     }
    35     for(int i = 2; i < tot; i += 2){
    36         if(bridge[i])
    37             printf("%d %d\n", ver[i ^ 1], ver[i]);
    38     }
    39 }

## **割点判定法则**： ##

若$x$不是搜索树的根节点，则$x$是割点当且仅当搜索树上存在$x$的一个子节点$y$，满足：$dfn\[x\]\\leq low\[y\]$

特别地，若$x$是搜索树地根节点，则$x$是割点当且仅当搜索树上存在至少两个子节点$y\_1,y\_2$满足上述条件。

1 #include<cstdio>
     2 #include<cstdlib>
     3 #include<map>
     4 #include<set>
     5 #include<cstring>
     6 #include<algorithm>
     7 #include<vector>
     8 #include<cmath> 
     9 #include<stack>
    10 #include<queue>
    11 #include<iostream>
    12 
    13 #define inf 0x7fffffff
    14 using namespace std;
    15 typedef long long LL;
    16 typedef pair<int, int> pr;
    17 
    18 const int SIZE = 100010;
    19 int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
    20 int dfn[SIZE], low[SIZE], n, m, tot, num;
    21 bool bridge[SIZE * 2];
    22 
    23 void add(int x, int y)
    24 {
    25     ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
    26 }
    27 
    28 void tarjan(int x)
    29 {
    30     dfn[x] = low[x] = ++num;
    31     int flag = 0;
    32     for(int i = head[x]; i; i = Next[i]){
    33         int y = ver[i];
    34         if(!dfn[y]){
    35             tarjan(y);
    36             low[x] = min(low[x], low[y]);
    37             if(low[y] >= dfn[x]){
    38                 flag++;
    39                 if(x != root || flag > 1)cut[x] = true;
    40             }
    41         }
    42         else low[x] = min(low[x], dfn[y]);
    43     }
    44 }
    45 
    46 int main()
    47 {
    48     cin>>n>>m;
    49     tot = 1;
    50     for(int i = 1; i <= m; i++){
    51         int x, y;
    52         scanf("%d%d", &x, &y);
    53         if(x == y)continue;
    54         add(x, y);
    55         add(y, x);
    56     }
    57     for(int i = 1; i <= n; i++){
    58         if(!dfn[i]){
    59             root = i;
    60             tarjan(i);
    61         }
    62     }
    63     for(int i = 1; i <= n; i++){
    64         if(cut[i])printf("%d", i);
    65     }
    66     puts("are cut-vertexes");
    67 }

## **双连通分量** ##

若一张无向连通图不存在割点，则称它为“**点双连通图**”。若一张无向连通图不存在桥，则称他为“**边双连通图**”。

无向图的极大点双连通子图被称为“**点双连通分量**”，简记为v-DCC。无向连通图的极大边双连通子图被称为“**边双连通分量**”，简记为e-DCC。

**定理1**一张无向连通图是点双连通图，当且仅当满足下列两个条件之一：

1.图的顶点数不超过2.

2.图中任意两点都同时包含在至少一个简单环中。

**定理2**一张无向连通图是边双连通图，当且仅当任意一条边都包含在至少一个简单环中。

### 边双连通分量求法 ###

求出无向图中所有的桥，删除桥后，每个连通块就是一个边双连通分量。

用Tarjan标记所有的桥边，然后对整个无向图执行一次深度优先遍历（不访问桥边），划分出每个连通块。

1 int c[SIZE], dcc;
     2 
     3 void dfs(int x){
     4     c[x] = dcc;
     5     for(int i = head[x]; i; i = Next[i]){
     6         int y = ver[i];
     7         if(c[y] || bridge[i])continue;
     8         dfs(y);
     9     }
    10 }
    11 
    12 //main()
    13 for(int i = 1; i <= n; i++){
    14     if(!c[i]){
    15         ++dcc;
    16         dfs(i);
    17     }
    18 }
    19 printf("There are %d e-DCCs.\n", dcc);
    20 for(int i = 1; i <= n; i++){
    21     printf("%d belongs to DCC %d.\n", i, c[i]);
    22 }

### e-DCC的缩点 ###

把e-DCC收缩为一个节点，构成一个新的树，存储在另一个邻接表中。

1 int hc[SIZE], vc[SIZE * 2], nc[SIZE * 2], tc;
     2 void add_c(int x, int y){
     3     vc[++tc] = y;
     4     nc[tc] = hc[x];
     5     hc[x] = tc;
     6 }
     7 
     8 //main()
     9 tc = 1;
    10 for(int i = 2; i <= tot; i++){
    11     int x = ver[i ^ 1];
    12     y = ver[i];
    13     if(c[x] == c[y])continue;
    14     add_c(c[x], c[y]);
    15 }
    16 printf("缩点之后的森林， 点数%d, 边数%d(可能有重边)\n", dcc, tc / 2);
    17 for(int i = 2; i < tc; i++){
    18     printf("%d %d\n", vc[i ^ 1], vc[i]);
    19 }

### 点双连通分量的求法 ###

桥不属于任何e-DCC，割点可能属于多个v-DCC

在Tarjan算法过程中维护一个栈，按照如下方法维护栈中的元素：

1.当一个节点第一次被访问时，该节点入栈。

2.当割点判定方法则中的条件$dfn\[x\]\\leq low\[y\]$成立时，无论$x$是否为根，都要：

（1）从栈顶不断弹出节点，直至节点$y$被弹出

（2）刚才弹出的所有节点与节点$x$一起构成一个v-DCC

1 void tarjan(int x){
     2     dfn[x] = low[x] = ++num;
     3     stack[++top] = x;
     4     iff(x == root && head[x] == 0){
     5         dcc[++cnt].push_back(x);
     6         return;
     7     }
     8     int flag = 0;
     9     for(int i = head[x]; i; i = Next[i]){
    10         int y = ver[i];
    11         if(!dfn[y]){
    12             tarjan(y);
    13             low[x] = min(low[x], low[y]);
    14             if(low[y] >= dfn[x]){
    15                 flag++;
    16                 if(x != root || flag > 1)cut[x] = true;
    17                 cnt++;
    18                 int z;
    19                 do{
    20                     z = stack[top--];
    21                     dcc[cnt].push_back(z);
    22 
    23                 }while(z != y);
    24                 dcc[cnt].push_back(x);
    25             }
    26         }
    27         else low[x] = min(low[x], dfn[y]);
    28     }
    29 }
    30 
    31 //main()
    32 for(int i = 1; i <= cnt; i++){
    33     printf("e-DCC #%d:", i);
    34     for(int j = 0; j < dcc[i].size(); j++){
    35         printf(" %d", dcc[i][j]);
    36     }
    37     puts("");
    38 }

### v-DCC的缩点 ###

设图中共有$p$个割点和$t$个v-DCC，新图将包含$p+t$个节点。

1 //main
     2 num = cnt;
     3 for(int i = 1; i <= n; i++){
     4     if(cnt[i])new_id[i] = ++num;
     5 }
     6 tc = 1;
     7 for(int i = 1; i <= cnt; i++){
     8     for(int j = 0; j < dcc[i].size(); j++){
     9         int x = dcc[i][j];
    10         if(cut[x]){
    11             add_c(i, new_id[x]);
    12             add_c(new_id[x], i);
    13         }
    14         else c[x] = i;
    15     }
    16 }
    17 printf("缩点之后的森林， 点数%d, 边数%d\n", num, tc / 2);
    18 printf("编号1~%d的为原图的v-DCC， 编号>%d的为原图割点\n", cnt, cnt);
    19 for(int i = 2; i < tc; i += 2){
    20     printf("%d %d\n", vc[i ^ 1], vc[i]);
    21 }

## 有向图的强连通分量 ##

一张有向图，若对于图中任意两个节点$x,y$，既存在$x$到$y$的路径，也存在$y$到$x$的路径，则称该有向图是**强连通图**。

有向图的极大强连通子图被称为**强连通分量**，简记为SCC。

一个环一定是强连通图，Tarjan算法的基本思路就是对每个点，尽量找到与它能构成环的所有节点。

Tarjan在深度优先遍历的同时维护了一个栈，当访问到节点$x$时，栈中需要保存一下两类节点：

1.搜索树上$x$的祖先节点，记为$anc(x)$

2.已经访问过，并且存在一条路径到达$anc(x)$的节点

实际上栈中的节点就是能与从$x$出发的“后向边”和“横叉边”形成环的节点。

### 追溯值： ###

定义为满足一下条件的节点的最小时间戳：

1.该点在栈中。

2.存在一条存subtree(x)出发的有向边，以该点为终点。

**计算步骤：**

1.当节点$x$第一次被访问时，把$x$入栈，初始化$low\[x\]=dfn\[x\]$

2.扫描从$x$出发的每条边$(x,y)$

(1)若$y$没被访问过，则说明$(x,y)$是树枝边，递归访问$y$,从$y$回溯后，令$low\[x\] = min(low\[x\], low\[y\])$

(2)若$y$被访问过且$y$在栈中，令$low\[x\] = min(low\[x\], dfn\[y\])$

3.从$x$回溯之前，判断是否有$low\[x\] = dfn\[x\]$。若成立，则不断从栈中弹出节点直至$x$出栈。

### 强连通分量判定法则 ###

追溯值计算过程中，若从$x$回溯前，有$low\[x\] = dfn\[x\]$成立，则栈中从$x$到栈顶的所有节点构成一个强连通分量。

如果$low\[x\]=dfn\[x\]$，说明$subtree(x)$中的节点不能与栈中其他节点一起构成环。另外，因为横叉边的终点时间戳必定小于起点时间戳，所以$subtree(x)$中的节点也不可能直接到达尚未访问的节点（时间戳更大）

1 const int N = 100010, M = 1000010;
     2 int ver[M], Next[M], head[N], dfn[N], low[N];
     3 int stack[N], ins[N], c[N];
     4 vector<int>scc[N];
     5 int n, m, tot, num, top, cnt;
     6 
     7 void add(int x, int y){
     8     ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
     9 }
    10 
    11 void tarjan(int x){
    12     dfn[x] = low[x] = ++num;
    13     stack[++top] = x, ins[x] - 1;
    14     for(int i = head[x]; i; i = Next[i]){
    15         if(!dfn[ver[i]]){
    16             tarjan(ver[i]);
    17             low[x] = min(low[x], low[ver[i]]);
    18         }else if(ins[ver[i]]){
    19             low[x] = min(low[x], dfn[ver[i]]);
    20         }
    21     }
    22     if(dfn[x] == low[x]){
    23         cnt++;
    24         int y;
    25         do{
    26             y = stack[top--], ins[y] = 0;
    27             c[y] = cnt, scc[cnt].push_back(y);
    28         }while(x != y);
    29     }
    30 }
    31 
    32 int main(){
    33     cin>>n>>m;
    34     for(int i = 1; i <= m; i++){
    35         int x, y;
    36         scanf("%d%d", &x, &y);
    37         add(x, y);
    38     }
    39     for(int i = 1; i <= n; i++){
    40         if(!dfn[i])tarjan(i);
    41     }
    42 }

### 缩点 ###

1 void add_c(int x, int y){
     2     vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc;
     3 }
     4 
     5 //main
     6 for(int x = 1; x <= n; x++){
     7     for(int i = head[x]; i; i = Next[i]){
     8         int y = ver[i];
     9         if(c[x] == c[y])continue;
    10         add_c(c[x], c[y]);
    11     }
    12 }

李煜东的[《图连通性若干扩展问题探讨》][Link 1]，有点难。

转载于:https://www.cnblogs.com/wyboooo/p/11061928.html

[Link 1]: https://wenku.baidu.com/view/b06471d019e8b8f67d1cb91b.html