POJ 1611(并查集)

内容目录

唯一的WA

是把0的父亲当成祖先

father[x]getfather(x)差别巨大啊

Program p1611;
const
   maxn=30010;
   maxm=500;
var
   n,m,i,j,k,p1,p2,ans,f0:longint;
   father:array[0..maxn] of longint;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
procedure union(x,y:longint);
begin
   if getfather(x)<>getfather(y) then
      father[father[x]]:=father[father[y]];
end;
begin
   read(n,m);
   while (n+m>0) do
   begin
      for i:=0 to n-1 do father[i]:=i;
      for i:=1 to m do
      begin
         read(k);
         if k>0 then read(p1);
         if k>1 then
            for j:=2 to k do
            begin
               read(p2);
               union(p1,p2);
            end;
      end;
      ans:=1;
      f0:=getfather(0);
      for i:=1 to n-1 do if getfather(i)=f0 then inc(ans);
      writeln(ans);
      read(n,m);
   end;
end.