1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 #include<queue>
5 #include<stack>
6 #include<vector>
7 using namespace std;
8 const int maxn=
100005;
//边数
9 const int maxn1=
1005;
//顶点数
10 struct edge{
11 int from;
12 int to;
13 int next;
14 }EDGE[maxn];
15 vector<
int>
vc[maxn1];
16 int head[maxn1],dfn[maxn1],vis[maxn1],low[maxn1],col[maxn1],
out[maxn1],
in[maxn1],en[maxn1],stk[maxn1];
//各个变量的意义可参照上篇博客
17 int edge_cnt=
0,tot1=
0,tot2=
0,scc_cnt=
0,tot0=
0;
18 void add(
int x,
int y)
19 {
20 EDGE[edge_cnt].
from=
x;
21 EDGE[edge_cnt].to=
y;
22 EDGE[edge_cnt].next=
head[x];
23 head[x]=edge_cnt++
;
24 }
25 void Tarjan(
int u)
26 {
27 low[u]=dfn[u]=++tot1;
//注意tot1的初值必须是1【因为dfn必须为正数】，所以这里使用++tot1而不用tot1++;
28 vis[u]=
1;
29 stk[++tot2]=
u;
30 for(
int i = head[u]; i != -
1 ; i =
EDGE[i].next)
31 {
32 if(!
dfn[EDGE[i].to]){
33 Tarjan(EDGE[i].to);
34 low[u]=
min(low[u],low[EDGE[i].to]);
35 }
36 else if(vis[EDGE[i].to]){
37 low[u]=
min(low[u],low[EDGE[i].to]);
38 }
39 }
40 if(low[u]==
dfn[u]){
41 int xx;
42 scc_cnt++;
//注意scc_cnt也是从1开始的，因为要染色，区别于为染色的0
43 do{
44 xx=stk[tot2--
];
45 vc[scc_cnt].push_back(xx);
46 col[xx]=
scc_cnt;
47 vis[xx]=
0;
48 }
while(xx!=
u);
49 }
50 }
51 void INIT()
52 {
53 for(
int i =
0 ; i < maxn1 ; i++
)
54 vc[i].clear();
55 edge_cnt=
0,tot1=
0,tot2=
0,scc_cnt=
0,tot0=
0;
56 memset(head,-
1,
sizeof(head));
57 memset(stk,
0,
sizeof(stk));
58 memset(
in,
0,
sizeof(
in));
59 memset(
out,
0,
sizeof(
out));
60 memset(dfn,
0,
sizeof(dfn));
61 memset(low,
0,
sizeof(low));
62 memset(col,
0,
sizeof(col));
63 }
64 void suodian()
//缩点
65 {
66 for(
int i =
0 ; i < edge_cnt ; i++
)
67 {
68 if(col[EDGE[i].
from]!=
col[EDGE[i].to])
69 {
70 in[col[EDGE[i].to]]++;
//缩点
71 out[col[EDGE[i].
from]]++
;
72 }
73 }
74 }
75 int main()
76 {
77 int n,m;
78 scanf(
"%d%d",&n,&
m);
79 INIT();
80 while(m--
)
81 {
82 int a,b;
83 scanf(
"%d%d",&a,&
b);
84 add(a,b);
85 }
86 for(
int i =
1 ; i <= n; i++
)
87 {
88 if(!
dfn[i])Tarjan(i);
89 }
90 suodian();
91 return 0;
92 }
93 /*4 5
94 1 3
95 2 4
96 4 2
97 1 4
98 2 1*/
转载于:https://www.cnblogs.com/MekakuCityActor/p/8987108.html
