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