记录编号	85020	评测结果	AAAAAAAAAAA
题目名称	[USACO 5.3] 校园网	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2013-12-23 20:45:25	内存使用	0.31 MiB

#include <fstream>
#include <list>

using namespace std;

ifstream in("schlnet.in");
ofstream out("schlnet.out");

int n;
list<int> map[101];
list<int> rmap[101];

void input();
void proc();

int main()
{
	input();
	proc();
	return 0;
}

void input()
{
	in>> n;
	register int itemp;
	for(int i=1; i!=n+1; ++i)
	{
		in>> itemp;
		while(itemp!=0)
		{
			map[i].push_back(itemp);
			rmap[itemp].push_back(i);
			in>> itemp;
		}
	}
	return ;
}

int *used;
list<int> f;
int *ref;
int *res;

void dfsf(int a)
{
	used[a]=1;
	for(list<int>::iterator it=map[a].begin(); it!=map[a].end(); ++it)
	{
		if(!used[*it])
		{
			dfsf(*it);
		}
	}
	f.push_front(a);
	return ;
}

void dfss(int a, int r)
{
	used[a]=1;
	for(list<int>::iterator it=rmap[a].begin(); it!=rmap[a].end(); ++it)
	{
		if(!used[*it])
		{
			ref[*it]=r;
			dfss(*it, r);
		}
	}
	return ;
}

void debug(int i)

{
	used[i]=1;
	for(list<int>::iterator it=map[i].begin(); it!=map[i].end(); ++it)
	{
		if(!used[*it]&&!map[*it].empty())
		{
			out<< *it<< ' ';
			debug(*it);
		}
	}
	return ;
}

void proc()
{
	used=new int [n+1];
	ref=new int[n+1];
	res=new int[n+1];
	int *ctin=new int[n+1];
	int *ctout=new int [n+1];
	for(int i=1; i!=n+1; ++i)
	{
		used[i]=0;
		res[i]=0;
		ctin[i]=0;
		ctout[i]=0;
	}
	for(int i=1; i!=n+1; ++i)
	{
		if(!used[i])
		{
			dfsf(i);
		}
	}
	for(int i=1; i!=n+1; ++i)
	{
		used[i]=0;
	}
	int rest(0);
	for(list<int>::iterator it=f.begin(); it!=f.end(); ++it)
	{	
		if(!used[*it])
		{
			res[*it]=1;//缩点结果
			++rest;
			used[*it]=1;
			if(!rmap[*it].empty())
			{
				ref[*it]=*it;
				dfss(*it, *it);
			}
			else
			{
				ref[*it]=*it;
			}
		}
	}
	/*
	for(int i=1; i!=n+1; ++i)
	{
		out<<i <<':' << ref[i]<< ' ';
	}
	out<< endl;
	for(int i=1; i!=n+1; ++i)
	{
		out<< res[i]<< ' ';
	}
	out<< endl;
	*/
	if(rest==1)
	{
		out<< 1<< endl;
		out<< 0<< endl;
		return ;
	}
	int icount(0);
	int ocount(0);
	for(int i=1; i!=n+1; ++i)
	{
		list<int>::iterator it(map[i].begin());
		while(it!=map[i].end())
		{
			if(ref[*it]!=ref[i])
			{
				ctin[ref[i]]=1;
				break;
			}
			++it;
		}
		it=rmap[i].begin();
		while(it!=rmap[i].end())
		{
			if(ref[*it]!=ref[i])
			{
				ctout[ref[i]]=1;
				break;
			}
			++it;
		}
	}
	for(int i=1; i!=n+1; ++i)
	{
		if(res[i])
		{
			if(ctin[i]==0)
			{
				++icount;
			}
			if(ctout[i]==0)
			{
				++ocount;
				/*for(int j=1; j!=n+1; ++j)
				{
					used[j]=0;
				}
				out<< i<< ' ';
				debug(i);
				out<< endl;*/
			}
		}
	}
	out<< ocount<< endl;
	out<< (icount>ocount?icount:ocount)<< endl;
	return ;
}