2013-11-16 11:39
原题传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1051
强连通分量，缩完点之后看出度为0的强连通分量有几个，如果只有一个则输出该强连通分量的点数，否则输出0；
/**************************************************************
Problem:
1051
User: BLADEVIL
Language: Pascal
Result: Accepted
Time:
124
ms
Memory:
1396
kb
****************************************************************/
//
By BLADEVIL
var
n, m :longint;
pre, other :
array
[
0
..
100010
]
of
longint;
last :
array
[
0
..
20010
]
of
longint;
l :longint;
flag :
array
[
0
..
10010
]
of
boolean;
dfn, low :
array
[
0
..
10010
]
of
longint;
time :longint;
tot :longint;
stack :
array
[
0
..
10010
]
of
longint;
key :
array
[
0
..
10010
]
of
longint;
size :
array
[
0
..
10010
]
of
longint;
full :longint;
father :
array
[
0
..
20010
]
of
longint;
function
min(a,b:longint):longint;
begin
if
a>b
then
min:=b
else
min:=
a;
end
;
procedure
connect(x,y:longint);
begin
inc(l);
pre[l]:
=
last[x];
last[x]:
=
l;
other[l]:
=
y;
end
;
procedure
init;
var
i :longint;
x, y :longint;
begin
read(n,m);
for
i:=
1
to
m
do
begin
read(x,y);
connect(y,x);
end
;
end
;
procedure
dfs(x:longint);
var
q, p :longint;
cur :longint;
begin
inc(time);
dfn[x]:
=
time;
low[x]:
=
time;
flag[x]:
=
true;
inc(tot);
stack[tot]:
=
x;
q:
=
last[x];
while
q<>
0
do
begin
p:
=
other[q];
if
dfn[p]=
0
then
begin
dfs(p);
low[x]:
=
min(low[x],low[p]);
end
else
if
flag[p]
then
low[x]:=
min(low[x],dfn[p]);
q:
=
pre[q];
end
;
cur:
=-
1
;
if
dfn[x]=low[x]
then
begin
while
cur<>x
do
begin
cur:
=
stack[tot];
dec(tot);
flag[cur]:
=
false;
key[cur]:
=x+
n;
inc(size[key[cur]]);
end
;
end
;
end
;
procedure
main;
var
i :longint;
q, p :longint;
begin
for
i:=
1
to
n
do
if
dfn[i]=
0
then
dfs(i);
for
i:=
1
to
n
do
begin
q:
=
last[i];
while
q<>
0
do
begin
p:
=
other[q];
if
key[i]<>key[p]
then
begin
connect(key[i],key[p]);
father[key[p]]:
=
key[i];
end
;
q:
=
pre[q];
end
;
end
;
full:
=-
1
;
for
i:=
1
to
n
do
begin
if
(father[key[i]]=
0
)
and
(full=-
1
)
then
full:=
key[i];
if
(father[key[i]]=
0
)
and
(full<>-
1
)
and
(full<>key[i])
then
begin
writeln(
0
);
exit;
end
;
end
;
writeln(size[full]);
end
;
begin
init;
main;
end
.
