cubes.pas

Magio牛的usaco源代码

program cubes;
const
  max=30000;
var
  fin,fout:text;
  rt,fr,l:array[1..max]of integer;
  p,i:longint;
  op:char;
  x,y:integer;
procedure pathcomp(x:integer);
  var
    root,sum,t:integer;
  begin
    root:=x;sum:=0;
    while rt[root]<>root do begin
      inc(sum,fr[root]);
      root:=rt[root];
    end;
    while x<>root do begin
      t:=fr[x];
      fr[x]:=sum;
      dec(sum,t);
      t:=rt[x];
      rt[x]:=root;
      x:=t;
    end;
  end;
procedure move(x,y:integer);
  var
    r1,r2:integer;
  begin
    pathcomp(x);
    pathcomp(y);
    r1:=rt[x];r2:=rt[y];
    rt[r2]:=r1;
    fr[r2]:=l[r1];
    inc(l[r1],l[r2]);
  end;
procedure count(x:integer);
  begin
    pathcomp(x);
    writeln(fout,l[rt[x]]-fr[x]-1);
  end;
begin
  assign(fin,'cubes.in');
  reset(fin);
  assign(fout,'cubes.out');
  rewrite(fout);

  for i:=1 to max do begin
    rt[i]:=i;
    fr[i]:=0;
    l[i]:=1;
  end;

  readln(fin,p);
  for i:=1 to p do begin
    read(fin,op);
    case op of
      'M':begin
            readln(fin,x,y);
            move(x,y);
          end;
      'C':begin
            readln(fin,x);
            count(x);
          end;
    end;
  end;

  close(fin);
  close(fout);
end.