ac1208.pas

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

program tju1208;
const
  maxn=50000;
  kinds=3;
var
  root:array[1..maxn]of word;
  rel:array[1..maxn]of byte;
  n,k,i,lies,d,x,y:longint;
procedure pathcomp(x:word);
  var
    r,t,d:word;
  begin
    r:=x;d:=0;while root[r]<>r do begin
      inc(d,rel[r]);r:=root[r];
    end;
    d:=d mod kinds;
    while root[x]<>r do begin
      t:=rel[x];rel[x]:=d;d:=(d-t+kinds) mod kinds;
      t:=root[x];root[x]:=r;x:=t;
    end;
  end;
begin
  repeat
    read(n,k);lies:=0;
    for i:=1 to n do begin
      root[i]:=i;rel[i]:=0;
    end;
    for i:=1 to k do begin
      read(d,x,y);
      if (x>n) or (y>n) or (d=2) and (x=y) then begin inc(lies);continue;end;
      if (d=1) and (x=y) then continue;
      pathcomp(x);pathcomp(y);
      if root[x]<>root[y] then begin
        rel[root[y]]:=(ord(d=2)+rel[x]-rel[y]+kinds) mod kinds;
        root[root[y]]:=root[x];
      end
      else if (d=1) and (rel[x]<>rel[y]) or
              (d=2) and ((rel[y]-rel[x]+kinds) mod kinds<>1) then inc(lies);
    end;
    writeln(lies);
  until seekeof;
end.