1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=
100005;
4 int cnt=
0;
//强连通分量的个数
5 int stk[maxn];
//暂时存放遍历过的点,在遇到low[x]==dfn[x]时向外抛出元素
6 int dfn[maxn];
//时间戳[由于每个点最多属于一个强连通分量,所以也用来区分是否已经存在于一个强连通分量了,如果存在就没必要继续向下查找了]
7 int low[maxn]
//和最早祖先的时间
8 int vis[maxn];
//标记本次遍历过程入栈的点,在stk[]抛出点时同时清除标记的印记
9 int sz[maxn];
//每个强连通分量内元素的个数
10 int tim=
1;
11 void tar(
int x)
12 {
13 low[x]=dfn[x]=tim++
;
14 vis[x]=
1;
15 stk[tot++]=
x;
16 if(!
dfn[next[x]])
17 {
18 tar(next[x]);
19 low[x]=
min(low[x],low[next[x]]);
20 }
21 else if(vis[next[x]])
22 {
23 low[x]=min(low
[next[x]],low[x]);
24 }
25 if(dfn[x]==
low[x])
26 {
27 int xx;
28 cnt++
;
29 do{
30 xx=stk[--tot];
//抛出元素
31 col[xx]=cnt;
//涂色分块
32 sz[cnt]++;
//元素所在强连通分量内元素的个数
33 vis[xx]=
0;
//清除标记
34 }
while(x!=
xx);
35 }
36 }
37 int main()
38 {
39 for(
int i =
1 ; i <= n ; i++
)
40 {
41 tar(i);
42 }
43 return 0;
44 }
转载于:https://www.cnblogs.com/MekakuCityActor/p/8982349.html
相关资源:各显卡算力对照表!
转载请注明原文地址: https://win8.8miu.com/read-9269.html