记录编号	8779	评测结果	AAAAAAAAAA
题目名称	[POI 1999] 遗传密码	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.095 s
提交时间	2008-12-15 22:03:29	内存使用	0.28 MiB

/* 
 * Problem: POI1999 pie
 * Author: Guo Jiabao
 * Time: 2008.
 * State: Unsolved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=1001;

class tUFS
{
	public:
	int F[MAXN];
	tUFS()
	{
		for (int i=1;i<MAXN;i++)
			F[i]=-i;
	}
	int findroot(int a)
	{
		int r=a,t;
		while (F[r]>0) r=F[r];
		while (F[a]>0) {t=F[a];F[a]=r;a=t;}
		return r;
	}
	void Union(int a,int b)
	{
		F[findroot(a)]=findroot(b);
	}
	bool Judge(int a,int b)
	{
		return F[findroot(a)]==F[findroot(b)];
	}
	int getroot(int a)
	{
		return -F[findroot(a)];
	}
};

int M,PC,Ans;
int ind[MAXN],oud[MAXN];
bool app[MAXN],P[MAXN];
int A[MAXN],Q[MAXN];
tUFS U;

void init()
{
	int i,a,b;
	freopen("pie.in","r",stdin);
	freopen("pie.out","w",stdout);
	scanf("%d",&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		oud[a]++; ind[b]++;
		app[a]=app[b]=true;
		if (!U.Judge(a,b))
			U.Union(a,b);
	}
}

void solve()
{
	int i,k,v;
	for (i=1;i<MAXN;i++)
	{
		if (app[i])
		{
			k=U.getroot(i);
			if (!P[k])
			{
				P[k]=true;
				Q[++PC]=k;
			}
			v=ind[i]-oud[i]; if (v<0) v=-v;
			A[k]+=v;
		}
	}
	Ans=M;
	if (PC==(i=1))
	{
		if (A[Q[i]]==0)
			Ans++;
		else
			Ans+=A[Q[i]]/2;
	}
	else
	{
		for (i=1;i<=PC;i++)
		{
			if (A[Q[i]]==0)
				Ans++;
			else
				Ans+=A[Q[i]]/2;
		}
	}
}

int main()
{
	init();
	solve();
	printf("%d",Ans);
	return 0;
}