图论的实际应用之四 割点 (300分)

Q

qinjlin76

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #21

我不会怎么办，问题在哪？

 

Q

qinjlin76

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #22

const maxn=20;
s=1;
type node=record
dfn,low,flag:integer;
end;
var g:array[1..maxn,1..maxn] of 0..1;
p:array[1..maxn] of node;
r:array[1..maxn] of 0..1;
i,j,n,dfn:integer;
function low(x:integer):integer;
var i,j,k:integer;
begin
dfn:=dfn+1;
p[x].dfn:=dfn;
p[x].low:=dfn;
p[x].flag:=1;
if x=s then
begin
j:=0;
for i:=1 to ndo
if (g[x,i]=1) and (p.flag=0) then
begin
j:=j+1;
k:=low(i);
end;
if j>1 then
r[x]:=1;
end else
begin
j:=0;
for i:=1 to ndo
if g[x,i]=1 then
if p.flag=0 then
begin
k:=low(i);
if k>=p[x].dfn then
j:=j+1;
if p[x].low>k then
p[x].low:=k;
end
else
if p[x].dfn>p.dfn then
if p[x].low>p.dfn then
p[x].low:=p.dfn;
if j>0 then
r[x]:=1;
end;
p[x].flag:=2;
low:=p[x].low;
end;

begin
fillchar(p,sizeof(p),0);
read;
for i:=1 to ndo
for j:=1 to ndo
read(g[i,j]);
dfn:=0;
fillchar(r,sizeof(r),0);
i:=low(1);
for i:=1 to ndo
if r=1 then
write(i,' ');
writeln;
end.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #23

to qinjlin76:
呵呵，不好好带孩子，却跑来灌水

 

Q

qinjlin76

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #24

宽带已申请，这两天来装。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #25

呵呵，装好了联系起来就方便了。

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #26

我感觉程序写得太乱，下次求桥的时候再改改

 

Q

qinjlin76

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #27

你的QQ号？

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-07-02

• #28

35165906