图论的实际应用之五 桥(300分)

虽然通过
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1954974
的程序找到了美英联军最关键的据点,但伊军很快发现,联军防备森严,自己实在没有实力夺下城镇.但伊军同时发现,联军在城外的通讯线路上的防御要差的多,因此,请你重新写一程序,看看能否破坏一条线路就能达到上题的目的.如果能,请指出破坏哪两个城市间的线路.

以下程序在Win2K+Tp7.0下测试通过。
const maxn=20;
type node=record
dfn,low,flag:integer;
end;
var g:array[1..maxn,1..maxn] of integer;
p:array[1..maxn] of node;
r:array[1..maxn,1..maxn] of 0..1;
i,j,n,dfn,num:integer;
procedure visit(x:integer);
var i,j:integer;
begin
dfn:=dfn+1;
p[x].dfn:=dfn;
p[x].low:=dfn;
p[x].flag:=1;
for i:=1 to ndo
if g[x,i]=1 then
if (p[x].dfn<p.dfn) or (p.dfn=0) then
begin
if p.flag=0 then
begin
g[i,x]:=-1;
visit(i);
if p.low>=p.dfn then
r[x,i]:=1;
end;
if p[x].low>p.low then
p[x].low:=p.low;
end else
if p[x].low>p.dfn then
p[x].low:=p.dfn;
p[x].flag:=2;
end;

begin
fillchar(p,sizeof(p),0);
fillchar(r,sizeof(r),0);
dfn:=0;
num:=0;
read;
for i:=1 to ndo
for j:=1 to ndo
read(g[i,j]);
visit(1);
for i:=1 to ndo
for j:=1 to ndo
if r[i,j]=1 then

begin
write(i,'-->',j,' ');
num:=num+1;
end;
if num=0 then
writeln('none') else
writeln;
end.