> program p1470;
>  const
>   maxn=1000;
>   maxq=10000;
>  var
>   q:array[1..maxn,0..maxq] of longint;
>   son:array[1..maxn,0..maxn] of longint;
>   ans,h:array[1..maxn] of longint;
>   flag:array[1..maxn] of boolean;
>   root,n,m:longint;
>   
>  procedure init;
>   var i,j,x,y:longint;
>    ch:char;
>    
>    function ru:longint;
>     begin
>      ch:='.'; ru:=0;
>      while not (ch in ['0'..'9']) do read(ch);
>      repeat
>       ru:=ru*10+ord(ch)-48;
>       read(ch);
>      until not (ch in ['0'..'9']);
>     end;
>    
>   begin
>    for i:=1 to n do h[i]:=0;
>    for i:=1 to n do q[i,0]:=0;
>    for i:=1 to n do ans[i]:=0;
>    for i:=1 to n do flag[i]:=false;
>    for i:=1 to n do
>      begin
>       x:=ru;
>       son[x,0]:=ru;
>       for j:=1 to son[x,0] do
>        begin
>          read(son[x,j]);
>          inc(h[son[x,j]]);
>        end;
>       readln;
>      end;
>    for i:=1 to n do
>     if h[i]=0 then root:=i;
>    readln(m);
>    repeat
>     dec(m);
>     x:=ru; y:=ru;
>     if x=y then
>      begin inc(ans[x]); continue; end;
>     inc(q[x,0]); q[x,q[x,0]]:=y;
>     inc(q[y,0]); q[y,q[y,0]]:=x;
>     if eoln then readln;
>    until (m=0) or eof;
>    for i:=1 to n do h[i]:=i;
>   end;
> 
>  function find(p:longint):longint;
>   begin
>    if h[p]=p then exit(p);
>    find:=find(h[p]);
>    h[p]:=find;
>   end;
> 
>  procedure tarjan(t:longint);
>   var i,j:longint;
>   begin
>    flag[t]:=true; h[t]:=t;
>    for i:=1 to q[t,0] do
>     if flag[q[t,i]] then inc(ans[find(q[t,i])]);
>    for i:=1 to son[t,0] do
>     begin
>      tarjan(son[t,i]);
>      h[son[t,i]]:=t;
>     end;
>   end;
> 
>  procedure print;
>   var i:longint;
>   begin
>    for i:=1 to n do
>     if ans[i]>0 then writeln(i,':',ans[i]);
>   end;
>     
>  begin
> 
>    while not eof do
>      begin
>       readln(n);
>       if n=0 then break;
>       init;
>       tarjan(root);
>       print;
>      end;
> 
>  end.

• Re:谁能帮我看下我的程序哪处有问题？tarjan算法，交了n次，就是过不了 (46) sfys 2011-08-03 10:50:54
  • Re:谁能帮我看下我的程序哪处有问题？tarjan算法，交了n次，就是过不了 (23) lixl 2011-08-03 10:53:29