2013-11-16 11:39
原題傳送門 http://www.lydsy.com/JudgeOnline/problem.php?id=1051
強連通分量，縮完點之后看出度為0的強連通分量有幾個，如果只有一個則輸出該強連通分量的點數(shù)，否則輸出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
.
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
