tarjan算法是在dfs生成一颗dfs树的时候按照访问顺序的先后，为每个结点分配一个时间戳，然后再用low[u]表示结点能访问到的最小时间戳

以上的各种应用都是在此拓展而来的。

 

割点：如果一个图去掉某个点，使得图的连通分支数增加，那么这个点就是割点

某个点是割点，当且仅当这个点的后代没有连回自己祖先的边。即low[v] >= dfn[u]     ， v是u的后代

需要注意的是根结点的特判，因为根结点没有祖先，根结点是割点，当且仅当根结点有两个以上的儿子。

问题：重边对该算法有影响吗？没有影响。 

　　　需要注意的地方？ 图至少有三个点以上， 否则需要注意一下。

　　

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 1000 + 10;
17 vector<int> g[N];
18 int dfs_clock,dfn[N],low[N];
19 bool isCut[N];
20 void init(int n)
21 {
22     dfs_clock = 0;
23     for(int i=0; i<=n; ++i)
24         dfn[i] = low[i] = isCut[i] = 0;
25 }
26 //重边对割点没有影响，且该算法对有向图同样适用
27 void tarjan(int u, int fa)
28 {
29     dfn[u] = low[u] = ++dfs_clock;
30     int child = 0;
31     for(int i=0; i<g[u].size(); ++i)
32     {
33         int v = g[u][i];
34         if(v==fa) continue;//如果是树枝边的反向访问，则不能用来更新low[u]
35         child++;
36         if(dfn[v]==0)
37             tarjan(v,u);
38         low[u] = min(low[u],low[v]);//用树枝边，或者后向边来跟新low[u]
39         if(low[v] >= dfn[u])
40             isCut[u] = true;
41     }
42     if(fa==-1 && child>=2) isCut[u] = true;
43 }
44 int main()
45 {
46     int n,m,i,u,v;
47     while(scanf("%d%d",&n,&m)!=EOF)
48     {
49         init(n);
50         for(i=0; i<m; ++i)
51         {
52             scanf("%d%d",&u,&v);
53             g[u].push_back(v);
54             g[v].push_back(u);
55         }
56         tarjan(1,-1);
57         for(i=1; i<=n; ++i)
58             if(isCut[i])
59                 printf("%d ",i);
60         puts("");
61     }
62     return 0;
63 }

View Code

 

割边：如果一个图去掉某条边，使得图的连通分支数增加，那么这条边就是割边（桥）

某条边是割边，当且仅当某个点的后代没有连回自己或者自己祖先的边，即low[v] > dfn[u],  那么边(u,v)是割边

问题：重边对该算法有影响吗？ 有影响。 所以要判断是不是有重边

　　

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 1000 + 10;
17 vector<int> g[N];
18 int dfs_clock,dfn[N],low[N],cntCut;
19 void init(int n)
20 {
21     cntCut = dfs_clock = 0;
22     for(int i=0; i<=n; ++i)
23     {
24         dfn[i] = low[i] = 0;
25         g[i].clear();
26     }    
27 }
28 //重边对割边有影响，比如有2--3  ,2--3两条边，那么边2--3就不是割边，因为去掉还是连通的，所以要判断一下
29 void tarjan(int u, int fa)
30 {
31     dfn[u] = low[u] = ++dfs_clock;
32     bool flag = false;
33     for(int i=0; i<g[u].size(); ++i)
34     {
35         int v = g[u][i];
36         if(v==fa && !flag)//在这里判断有没有重边
37         {
38             flag = true;
39             continue;
40         }
41         if(dfn[v]==0)
42             tarjan(v,u);
43         low[u] = min(low[u],low[v]);
44         if(low[v] > dfn[u])//这里统计的是割边的数量，如果要记录割边，那么就标记边，或者把边入栈
45             cntCut++;
46     }
47 }
48 int main()
49 {
50     int n,m,i,u,v;
51     while(scanf("%d%d",&n,&m)!=EOF)
52     {
53         init(n);
54         for(i=0; i<m; ++i)
55         {
56             scanf("%d%d",&u,&v);
57             g[u].push_back(v);
58             g[v].push_back(u);
59         }
60         tarjan(1,-1);
61         printf("%d\n",cntCut);
62     }
63     return 0;
64 }

View Code

 

点-双连通分量：如果任意两点存在两条点不重复的路径，那么就说这个图是点-双连通的。点-双连通的极大子图称为双连通分量

双连通分量之间的分界点是割点。而且双连通分量不可能分布在树根结点两端。所以我们将边入栈，当遇到割点时，就将边出栈，直到有边等于当前边。就跳出

问题：重边对该算法有影响吗？ 没有影响

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 #include <string>
 12 #include <math.h>
 13 using namespace std;
 14 typedef long long LL;                   
 15 const int INF = 1<<30;
 16 const int N = 1000 + 10;
 17 struct Edge
 18 {
 19     int u,v;
 20     Edge(){};
 21     Edge(int u, int v)
 22     {
 23         this->u = u;
 24         this->v = v;
 25     }
 26 };
 27 vector<int> g[N],bcc[N];
 28 int bccno[N],dfn[N],low[N],dfs_clock,cnt;
 29 stack<Edge> st;
 30 void init(int n)
 31 {
 32     cnt = dfs_clock = 0;
 33     for(int i=0; i<=n; ++i)
 34     {
 35         bccno[i] = low[i] = dfn[i] = 0;
 36         bcc[i].clear();
 37         g[i].clear();
 38     }    
 39 }
 40 void tarjan(int u, int fa)
 41 {
 42     dfn[u] = low[u] = ++dfs_clock;
 43     for(int i=0; i<g[u].size(); ++i)
 44     {
 45         int v = g[u][i];
 46         if(dfn[v]==0)
 47         {
 48             st.push(Edge(u,v));
 49             tarjan(v,u);
 50             low[u] = min(low[u],low[v]);
 51             if(low[v] >= dfn[u])//如果这个点是割点，那么先前入栈的一些边是属于一个双连通分量的
 52             {
 53                 Edge x;
 54                 cnt++;
 55                 for(;;)
 56                 {
 57                     x = st.top();
 58                     st.pop();
 59                     if(bccno[x.u] != cnt)
 60                     {
 61                         bccno[x.u] = cnt;
 62                         bcc[cnt].push_back(x.u);
 63                     }
 64                     if(bccno[x.v] != cnt)
 65                     {
 66                         bccno[x.v] = cnt;
 67                         bcc[cnt].push_back(x.v);
 68                     }
 69                     if(x.u==u && x.v==v)
 70                         break;
 71                 }
 72             }
 73         }    
 74         else if(v!=fa && dfn[v] < dfn[u])
 75         {
 76             st.push(Edge(u,v));
 77             low[u] = min(low[u],dfn[v]);
 78         }
 79         
 80     }
 81 }
 82 int main()
 83 {
 84     int n,m,i,u,v;
 85     while(scanf("%d%d",&n,&m)!=EOF)
 86     {
 87         init(n);
 88         for(i=0; i<m; ++i)
 89         {
 90             scanf("%d%d",&u,&v);
 91             g[u].push_back(v);
 92             g[v].push_back(u);
 93         }
 94         tarjan(1,-1);
 95         for(i=1; i<=cnt; ++i)
 96         {
 97             printf("bcc %d has vertex:",i);
 98             while(!bcc[i].empty())
 99             {
100                 printf("%d ",bcc[i].back());
101                 bcc[i].pop_back();
102             }
103             puts("");
104         }
105     }
106     return 0;
107 }

View Code

 

边-双连通分量：如果任意两点存在两条边不重复的路径，那么就说这个图是边-双连通的，边-双连通的极大子图成为边双连通分量。

边双连通分量的分界点是割边。双连通分量可以分布在根结点的两端。所以不能在for(int i=0; i<g[u].size(); ++i) 这个循环里面判断割边，而要在外面递归返回时判断

问题：重边对该算法有影响吗？有影响，就好像影响割边算法一样

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 1000 + 10;
17 vector<int> g[N];
18 stack<int> st;
19 int dfn[N],low[N],dfs_clock,bccno[N],cnt;
20 void init(int n)
21 {
22     cnt = dfs_clock = 0;
23     for(int i=0; i<n; ++i)
24     {
25         dfn[i] = low[i] = 0;
26         bccno[i] = 0;
27         g[i].clear();
28     }
29 }
30 
31 void tarjan(int u, int fa)//边双连通分量可能分布在某子树树根的两个分支上
32 {
33     low[u] = dfn[u] = ++dfs_clock;
34     st.push(u);
35     bool flag = 0;
36     for(int i=0; i<g[u].size(); ++i)
37     {
38         int v = g[u][i];
39         if(v==fa && !flag) //重边对边连通分量的判断有影响，所以要判断一下
40         {
41             flag = true;
42             continue;
43         }
44         if(dfn[v]==0)
45             tarjan(v,u);
46         low[u] = min(low[u],low[v]);
47     }
48     if(dfn[u]==low[u])//说明这个点的所有后代都没有连回自己祖先的边，
49     {
50         cnt++;
51         for(;;)
52         {
53             int x = st.top();
54             st.pop();
55             bccno[x] = cnt;
56             if(x==u)
57                 break;
58         }
59     }
60 }
61 int main()
62 {
63     int n,m,i,u,v;
64     while(scanf("%d%d",&n,&m)!=EOF)
65     {
66         init(n);
67         for(i=0; i<m; ++i)
68         {
69             scanf("%d%d",&u,&v);
70             g[u].push_back(v);
71             g[v].push_back(u);
72         }
73         tarjan(1,-1);
74         for(i=1; i<=n; ++i)
75             printf("vexter %d belong to bcc %d\n",i,bccno[i]);
76     }
77     return 0;
78 }

View Code

 问添加最少多少条边，使得整个图边-双连通， 首先求出边-双连通分量，然后缩点，最后变成一棵树，那么要加的边 就是（叶子结点+1)/2

强连通分量：如果有向图的任意两点可以，那么就说这个图是强连通的，一个图的极大子图是强连通的，那么就说这个子图是强连通分量

对于一个scc，我们要判断哪个点是该scc最先被发现的点，然后将后来发现的点出栈，知道遇到这个点。 那么出栈的点都属于一个强连通分量

问题：重边对该算法有影响吗？没有影响

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 1000 + 10;
17 vector<int> g[N];
18 stack<int> st;
19 int cnt,dfs_clock,dfn[N],low[N],sccno[N];
20 void init(int n)
21 {
22     cnt = dfs_clock = 0;
23     for(int i=0; i<=n; ++i)
24     {
25         dfn[i] = low[i] = sccno[i] = 0;
26         g[i].clear();
27     }
28 }
29 
30 void tarjan(int u, int fa)
31 {
32     dfn[u] = low[u] = ++dfs_clock;
33     st.push(u);
34     for(int i=0; i<g[u].size(); ++i)
35     {
36         int v = g[u][i];
37         if(dfn[v]==0)
38         {
39             tarjan(v,u);
40             low[u] = min(low[u],low[v]);
41         }    
42         else if(sccno[v]==0)//因为有向图存在横插边，不能用横插边来更新low[u]
43         {
44             low[u] = min(low[u],low[v]);
45         }
46     }
47     //同样，因为强连通分量可以分布在根结点的两个分支上，所以在递归返回的时候调用
48     if(low[u] == dfn[u])
49     {
50         cnt++;
51         for(;;)
52         {
53             int x = st.top();
54             st.pop();
55             sccno[x] = cnt;
56             if(x==u)
57                 break;
58         }
59     }
60 }
61 int main()
62 {
63     int n,m,i,u,v;
64     while(scanf("%d%d",&n,&m)!=EOF)
65     {
66         init(n);
67         for(i=0; i<m; ++i)
68         {
69             scanf("%d%d",&u,&v);
70             g[u].push_back(v);
71         }
72         tarjan(1,-1);
73         for(i=1; i<=n; ++i)
74             printf("vertex %d belong to scc %d\n",i,sccno[i]);
75     }
76     return 0;
77 }

View Code

 

版权声明：本文为justPassBy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/justPassBy/p/4442144.html