1 #include<cstdio>
2 #include<cstring>
3 #include<cstdlib>
4 #include<iostream>
5 #include<algorithm>
6 #define N 10000
7 using namespace std;
8 int x,y,n,m,t,tot,sum,top,time;
9 int head[N],col[N],stack[N],dfn[N],low[N],a[N][N];
10 bool vis[N];
11 struct Edge
12 {
13 int from,next,to;
14 }edge[N];
15 int add(
int x,
int y)
16 {
17 tot++
;
18 edge[tot].to=
y;
19 edge[tot].next=
head[x];
20 head[x]=
tot;
21 }
22 int read()
23 {
24 int x=
0,f=
1;
char ch=
getchar();
25 while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=
getchar();}
26 while(ch>=
'0'&&ch<=
'9'){x=x*
10+ch-
'0';ch=
getchar();}
27 return f*
x;
28 }
29 int tarjan(
int now)
30 {
31 //stack[]表示递归过程的栈，即用来判断该点是否已经加入到此次递归的栈中，在递归末尾，通过将vis置为false释放所有递归栈的元素
32 t=
0;
33 dfn[now]=low[now]=++time;
//初始每一个点的low值dfn等于它的时间戳
34 stack[++top]=now; vis[now]=
true;
//将该点入栈，标记为在栈中
35 for(
int i=head[now];i;i=edge[i].next)
//更新于他相连的点的low值
36 {
37 x=
edge[i].to;
38 if(vis[x]) low[now]=min(dfn[x],low[now]);
//如果该点已经在栈中,直接更新来到该点的那个点的low，不需要递归查询
39 else if(!
dfn[x])
40 {
41 tarjan(x);
42 low[now]=min(low[x],low[now]);
//不在栈中，需要从该点继续递归拓展
43 }
44 }
45 if(low[now]==dfn[now])
//说明以这个点结束强连通分量
46 {
47 sum++;
// 强连通分量的个数加一
48 col[now]=sum;
//将该点放在她所属的强连通分量了
49 for(;stack[top]!=now;top--
)
50 {
51 col[stack[top]]=
sum;
52 vis[stack[top]]=
false;
53 }
54 vis[now]=
false;
55 top--
;
56 }
57 }
58 int main()
59 {
60 n=read(),m=
read();
61 for(
int i=
1;i<=m;i++
)
62 {
63 x=read();y=
read();
64 add(x,y);
65 }
66 for(
int i=
1;i<=n;i++
)
67 if(!
dfn[i]) tarjan(i);
68 printf(
"%d",sum);
69 return 0;
70 }
View Code
转载于:https://www.cnblogs.com/MekakuCityActor/p/8855296.html
