ac1252.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 40 行

program tju1252;
const
  maxv=1000;
var
  root,deg,dif:array[0..maxv]of integer;
  v:array[0..maxv]of boolean;
  n,i,x,y:word;
procedure pathcomp(x:word);
  var
    r,t:word;
  begin
    r:=x;while root[r]<>r do r:=root[r];
    while x<>r do begin t:=root[x];root[x]:=r;x:=t;end;
  end;
begin
  repeat
    for i:=0 to maxv do root[i]:=i;
    fillchar(deg,sizeof(deg),0);
    fillchar(dif,sizeof(dif),0);
    fillchar(v,sizeof(v),0);

    read(n);
    for i:=1 to n do begin
      read(x,y);
      pathcomp(x);pathcomp(y);root[root[x]]:=root[y];
      inc(deg[x]);dec(deg[y]);
      v[x]:=true;v[y]:=true;
    end;

    for i:=0 to maxv do begin
      pathcomp(i);
      if deg[i]>0 then inc(dif[root[i]],deg[i]);
    end;
    for i:=0 to maxv do
      if v[i] and (root[i]=i) then
        if dif[i]>0 then inc(n,dif[i]) else inc(n);
    writeln(n);
  until seekeof;
end.