记录编号	127	评测结果	AAAAAAAAAA
题目名称	[POI 1999] 遗传密码	最终得分	100
用户昵称	francis	是否通过	通过
代码语言	Pascal	运行时间	0.083 s
提交时间	2008-04-25 11:26:32	内存使用	7.76 MiB

program pie;
const
max=1000; max1=1000000;
type
node=record
  na:longint;
  fa:longint;
  bo:boolean;
  end;
var
a:array[1..max]of node;
b:array[1..max]of longint;
c:array[1..max]of longint;
d:array[1..max1,1..2]of longint;
total,m,all,k,x,y,mx,n,i:longint;
f1,f2:text;

procedure init;
begin
assign(f1,'pie.in');
assign(f2,'pie.out');
reset(f1); rewrite(f2);
read(f1,n);
for i:=1 to n do
begin
inc(k);
read(f1,d[k,1],d[k,2]);
x:=d[k,1]; y:=d[k,2];
inc(b[x]); inc(c[y]);
if a[x].na=0 then begin inc(all); a[x].na:=all; a[x].fa:=-1;  end;
if a[y].na=0 then begin inc(all); a[y].na:=all; a[y].fa:=-1;  end;
if mx<y then mx:=y; if mx<x then  mx:=x;
end; end;

function find(k:longint):longint;
var
x,tmp:longint;
begin
x:=k;
while a[k].fa<>-1 do  k:=a[k].fa;
find:=k;
while a[x].fa<>-1 do
 begin
 tmp:=x; x:=a[x].fa;
 a[tmp].fa:=k;
 end;
end;

procedure he;
begin
for i:=1 to n do
begin
x:=find(d[i,1]); y:=find(d[i,2]);
if a[x].na<>a[y].na then begin a[y].fa:=x; dec(all); end;
end; end;

begin
init;
he;
for i:=1 to mx  do
if a[i].na>0 then
begin
x:=i;
while a[x].fa<>-1 do x:=a[x].fa;
if b[i]<>c[i] then a[x].bo:=true;
if b[i]>c[i] then total:=total+b[i] else total:=total+c[i];
end;

for i:=1 to mx do
if (a[i].fa=-1)and(a[i].bo=false) then inc(m);

total:=total+m;
write(f2,total);
close(f1); close(f2);
end.