poj 2816 用pascal 怎么过, 要详细代码,最好附上题解或者解释
发布网友
发布时间：2024-11-08 04:35
共1个回答
热心网友
时间：2024-11-08 05:08
【强连通tarjan算法】
（这是一种在图论中挺常用的算法，但省队以下的是基本不会考的，LZ需要的话可以百度一下模板以及讲解，实在不理解的话可以自己模拟几遍、、、）
http://www.cnblogs.com/pony1993/archive/2012/08/07/2627344.html
http://www.cnblogs.com/-sunshine/archive/2012/10/04/2711185.html
（以上两个网址包括tarjan算法的具体实现以及本题的解题报告）
----------------------------------------------------------------------------------------------------------------------
【下面附代码】：
var n,m,x,y,z,sum:longint;
s,t,a,b:array[1..50000]of longint;
o,p,q,fa,num,out:array[1..10000]of longint;
f:array[1..10000]of boolean;
//-------------------------------------------------分割线----------------------------------------------------------
function min(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
//-------------------------------------------------分割线----------------------------------------------------------
procere init;
var i,j,k:longint;
begin
readln(n,m);
for k:=1 to m do
begin
readln(i,j);
s[k]:=i;
t[k]:=j;
a[k]:=b[i];
b[i]:=k;
end;
end;
//-------------------------------------------------分割线----------------------------------------------------------
procere work(i:longint);
var j,k:longint;
begin
inc(x);p[i]:=x;q[i]:=x;
inc(y);o[y]:=i;f[i]:=true;
j:=b[i];
while j<>0 do
begin
k:=t[j];
if p[k]=0 then
begin
work(k);
q[i]:=min(q[i],q[k]);
end
else
if(p[k]<p[i])and(f[k])then
q[i]:=min(q[i],p[k]);
j:=a[j];
end;
if p[i]=q[i] then
begin
inc(z);
repeat
inc(num[z]);
k:=o[y];
dec(y);
f[k]:=false;
fa[k]:=z;
until k=i;
end;
end;
//-------------------------------------------------分割线----------------------------------------------------------
procere main;
var i,j,k:longint;
begin
for i:=1 to n do
if q[i]=0 then
work(i);
for i:=1 to n do
begin
j:=b[i];
while j<>0 do
begin
k:=t[j];
if fa[i]<>fa[k] then
inc(out[fa[i]]);
j:=a[j];
end;
end;
for i:=1 to z do
if out[i]=0 then
inc(sum);
if sum<>1 then writeln(0)
else
for i:=1 to z do
if out[i]=0 then
begin
writeln(num[i]);
break;
end;
end;
//-------------------------------------------------分割线----------------------------------------------------------
begin
init;
main;
end.
