求割点入门题!
……死调一下午+晚上才发现把‘node'打成’nodes'了……
Program P1523; const maxedge=999000; maxn=10000; var edge,tail:array[1..maxedge] of longint; size:longint; head:array[1..maxn] of longint; n,i,j,ans,k:longint; b,cut:array[1..maxn] of boolean; time,root:longint; a,d,ancestor,c:array[1..maxn] of longint; procedure addedge(u,v:longint); begin inc(size); edge[size]:=v; tail[size]:=head[u]; head[u]:=size; end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure Dfs(k,father,deep:longint); var i,j,p,tot:longint; begin tot:=0; c[k]:=1; d[k]:=deep; ancestor[k]:=deep; p:=head[k]; while (p>0) do begin i:=edge[p]; if (i<>father) and (c[i]=1) then ancestor[k]:=min(ancestor[k],d[i]); if (c[i]=0) then begin dfs(i,k,deep+1); inc(tot); ancestor[k]:=min(ancestor[k],ancestor[i]); if (k=root) and (tot>=2) then cut[k]:=true; if (k<>root) and (ancestor[i]>=d[k]) then cut[k]:=true; end; p:=tail[p]; end; c[k]:=2; inc(time); a[k]:=time; end; procedure Dfs2(k:longint); var i,p:longint; begin b[k]:=true; p:=head[k]; while (p>0) do begin i:=edge[p]; if not(b[i]) then begin dfs2(i); end; p:=tail[p]; end; end; function main:boolean; var i,j,p,ans:longint; begin time:=0; main:=false; for i:=1 to maxn do if (head[i]>0) and (c[i]=0) then begin root:=i; dfs(root,0,1); end; for i:=1 to maxn do if cut[i] then begin main:=true; ans:=0; fillchar(b,sizeof(b),false); b[i]:=true; p:=head[i]; while (p>0) do begin if not(b[edge[p]]) then begin dfs2(edge[p]); inc(ans); end; p:=tail[p]; end; writeln(' SPF node ',i,' leaves ',ans,' subnets'); end; end; begin { assign(input,'p1523.in'); reset(input); } k:=1; while not seekeof do begin size:=0; fillchar(head,sizeof(head),0); fillchar(edge,sizeof(edge),0); fillchar(tail,sizeof(tail),0); fillchar(cut,sizeof(cut),false); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); fillchar(ancestor,sizeof(ancestor),0); read(i); if i=0 then break; read(j); while (i>0) do begin addedge(i,j); addedge(j,i); read(i); if i=0 then break; read(j); end; ans:=0; writeln('Network #',k); if not(main) then writeln(' No SPF nodes'); writeln; inc(k); end; end.