1 program Xiong;
2 var
3 side:
array[
0..
100,
0..
100]
of boolean;
4 p:
array[
0..
100]
of boolean;
5 f:
array[
0..
100]
of longint;
6 n,m,i,t,a,b,ans,time:longint;
7
8 procedure dfs(m:longint);
9 var
10 i:longint;
11 begin
12 p[m]:=
true;
13 for i:=
1 to n
do
14 if (side[m,i])
and(p[i]=false)
then
15 dfs(i);
16 inc(time);
17 f[time]:=
m;
18 end;
19
20 procedure dfs2(m:longint);
21 var
22 i:longint;
23 begin
24 p[m]:=
false;
25 for i:=
1 to n
do
26 if side[i,m]
and(p[i])
then
27 dfs2(i);
28 end;
29
30 begin
31 assign(input,
'circle.in');reset(input);
32 assign(output,
'circle.out');rewrite(output);
33
34 readln(n,m);
35 for i:=
1 to m
do begin
36 read(a,b);
37 side[a,b]:=
true;
38 end;
39
40 for i:=
1 to n
do
41 if p[i]=false
then dfs(i);
42
43 for i:=n
downto 1 do
44 if p[f[i]]
then begin
45 inc(ans);
46 dfs2(f[i]);
47 end;
48 write(ans);
49
50 close(input);
51 close(output);
52 end.
感觉这个算法比tarjan好些多了，虽然可能慢一些，但是在数据范围不是很大的时候还是很实惠的嘛
转载于:https://www.cnblogs.com/xiong298/archive/2012/04/26/kosaraju.html
