ac1041.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1041;
const
  maxn=1500;
var
  last:array[0..maxn-1]of word;
  pre,child:array[1..maxn*2]of word;
  v:array[0..maxn-1]of boolean;
  yes,no:array[0..maxn-1]of word;
  t,u,n,i,j,k,x,y,c:word;
function min(a,b:word):word;
  begin
    if a<b then min:=a else min:=b;
  end;
procedure cal(x:word);
  var
    y:word;
  begin
    v[x]:=true;yes[x]:=1;no[x]:=0;
    while last[x]>0 do begin
      y:=child[last[x]];
      if not v[y] then begin
        cal(y);
        inc(yes[x],min(yes[y],no[y]));
        inc(no[x],yes[y]);
      end;
      last[x]:=pre[last[x]];
    end;
  end;
begin
  read(t);
  for u:=1 to t do begin
    fillchar(last,sizeof(last),0);
    fillchar(v,sizeof(v),0);

    read(n);c:=0;
    for i:=1 to n do begin
      read(x,k);
      for j:=1 to k do begin
        read(y);
        inc(c);pre[c]:=last[x];child[c]:=y;last[x]:=c;
        inc(c);pre[c]:=last[y];child[c]:=x;last[y]:=c;
      end;
    end;

    cal(0);
    writeln(min(yes[0],no[0]));
  end;
end.