求强连通块_Tarjan算法

求强连通块_Tarjan算法_C++

　　好久没有写算法了，就放一个 Tarjan 上来凑凑数哈

　　强连通块由若干个点组成，任意点与点之间可以之间或间接到达，显然可以看作一个环

　　下面是伪代码

　　强记：dfn为时间不变，low取最小，下一个dfn有值就跟dfn取min，没有就进去后跟low取，两个相等时弹栈

　　证明的话就贴一个

　　会不会证无所谓了，可以自己脑补一下，况且代码很好写

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #include<stack>
 8 #define N 100000
 9 using namespace std;
10 
11 stack<int> p;
12 int next[N],first[N],v[N],t,dfn[N],low[N];
13 bool f[N];
14 void dfs(int x)
15 {
16     p.push(x);
17     dfn[x]=low[x]=++t;
18     int i;
19     for (i=first[x];i;i=next[i])
20         if (f[v[i]]) continue;
21         if (dfn[v[i]]) low[x]=min(low[x],dfn[v[i]]);
22         else
23             {
24                 dfs(v[i]);
25                 low[x]=min(low[x],low[v[i]]);
26             }
27     if (low[x]==dfn[x])
28         {
29             while (p.top()!=x)
30                 {
31                     f[p.top()]=1;
32                     printf("%d ",p.top());
33                     p.pop();
34                 }
35             f[p.top()]=1;
36             p.pop();
37             printf("%d
",x);
38         }
39 }
40 int main()
41 {
42     freopen("tarjan.in","r",stdin);
43     freopen("tarjan.out","w",stdout);
44     int i,x,n,m;
45     scanf("%d%d",&n,&m);
46     for (i=1;i<=n;i++) f[i]=0;
47     for (i=1;i<=m;i++)
48         {
49             scanf("%d%d",&x,&v[i]);
50             next[i]=first[x];
51             first[x]=i;
52         }
53     for (i=1;i<=n;i++)
54         if (dfn[i]==0)
55             {
56                 t=0;
57                 dfs(i);
58             }
59     return 0;
60 }

QQ：740929894