Tarjan算法【阅读笔记】

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

割点判定法则：

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

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

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

双连通分量

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

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

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

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

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

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

边双连通分量求法

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

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

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

e-DCC的缩点

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

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

点双连通分量的求法

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

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

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

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

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

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

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

v-DCC的缩点

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

  1. 1 //main
  2.  2 num = cnt;
  3.  3 for(int i = 1; i <= n; i++){
  4.  4     if(cnt[i])new_id[i] = ++num;
  5.  5 }
  6.  6 tc = 1;
  7.  7 for(int i = 1; i <= cnt; i++){
  8.  8     for(int j = 0; j < dcc[i].size(); j++){
  9.  9         int x = dcc[i][j];
  10. 10         if(cut[x]){
  11. 11             add_c(i, new_id[x]);
  12. 12             add_c(new_id[x], i);
  13. 13         }
  14. 14         else c[x] = i;
  15. 15     }
  16. 16 }
  17. 17 printf("缩点之后的森林， 点数%d, 边数%d\n", num, tc / 2);
  18. 18 printf("编号1~%d的为原图的v-DCC， 编号>%d的为原图割点\n", cnt, cnt);
  19. 19 for(int i = 2; i < tc; i += 2){
  20. 20     printf("%d %d\n", vc[i ^ 1], vc[i]);
  21. 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. 1 const int N = 100010, M = 1000010;
  2.  2 int ver[M], Next[M], head[N], dfn[N], low[N];
  3.  3 int stack[N], ins[N], c[N];
  4.  4 vector<int>scc[N];
  5.  5 int n, m, tot, num, top, cnt;
  6.  6 
  7.  7 void add(int x, int y){
  8.  8     ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
  9.  9 }
  10. 10 
  11. 11 void tarjan(int x){
  12. 12     dfn[x] = low[x] = ++num;
  13. 13     stack[++top] = x, ins[x] - 1;
  14. 14     for(int i = head[x]; i; i = Next[i]){
  15. 15         if(!dfn[ver[i]]){
  16. 16             tarjan(ver[i]);
  17. 17             low[x] = min(low[x], low[ver[i]]);
  18. 18         }else if(ins[ver[i]]){
  19. 19             low[x] = min(low[x], dfn[ver[i]]);
  20. 20         }
  21. 21     }
  22. 22     if(dfn[x] == low[x]){
  23. 23         cnt++;
  24. 24         int y;
  25. 25         do{
  26. 26             y = stack[top--], ins[y] = 0;
  27. 27             c[y] = cnt, scc[cnt].push_back(y);
  28. 28         }while(x != y);
  29. 29     }
  30. 30 }
  31. 31 
  32. 32 int main(){
  33. 33     cin>>n>>m;
  34. 34     for(int i = 1; i <= m; i++){
  35. 35         int x, y;
  36. 36         scanf("%d%d", &x, &y);
  37. 37         add(x, y);
  38. 38     }
  39. 39     for(int i = 1; i <= n; i++){
  40. 40         if(!dfn[i])tarjan(i);
  41. 41     }
  42. 42 }

缩点

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

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

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

发表评论

表情：
评论列表 （有 0 条评论，427人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Tarjan 算法

    Tarjan 算法 一.算法简介 Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法，它能做到线性时间的复杂度。   我们定义： 如果

    一时失言乱红尘一时失言乱红尘/ 0 赞/ 183 阅读

    相关 Tarjan算法

     下面详细介绍一下Tarjan算法的基本思路： 　　　　　　1.任选一个点为根节点，从根节点开始。 　　　　　　2.遍历该点u所有子节点v，并标记这些子节点v已被访问

    超、凢脫俗超、凢脫俗/ 0 赞/ 310 阅读

    相关 tarjan算法 转载

    转载博主:[点击打开链接][Link 1] 讲的非常好，肯定可以看懂。 tarjan算法，一个关于 图的联通性的神奇算法。基于DFS（迪法师）算法，深度优先搜索一张有向图。

    蔚落蔚落/ 0 赞/ 284 阅读

    相关 tarjan算法讲解

    时隔好久回来复习tarjan算法，又看了许多网上的文章，在此再给一篇觉得不错的文章：[mengxiang000][] 全网最详细tarjan算法讲解，我不敢说别的。反正其他t

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 379 阅读

    相关 tarjan学习笔记

    1.$tarjan$求强连通分量 思想：在$dfs$的过程中，把强连通分量中的点入栈，当找到一个强连通分量的最起始的点，就将其所在强连通分量中的点出栈。 缩点 把强连通分

    小咪咪小咪咪/ 0 赞/ 356 阅读