记录编号	81859	评测结果	AAAAAAAAAAA
题目名称	[USACO 5.3] 校园网	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-11-18 22:02:55	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#include<cstring>
#include<deque>
#include<cstring>
#include<map>
#include<algorithm>
#include<iomanip>
using namespace std;
const int SIZEN=101;
class GRAPH{
public:
	int n;
	vector<int> c[SIZEN];//储存被指向边
	int ideg[SIZEN];
	int odeg[SIZEN];
	int dfn[SIZEN];
	int low[SIZEN];
	vector<int> st;
	bool instack[SIZEN];
	int index;
	int comsum;
	int belong[SIZEN];
	GRAPH(){
		n=0;
		for(int i=1;i<=n;i++) c[i].clear();
		memset(ideg,0,sizeof(ideg));
		memset(odeg,0,sizeof(odeg));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		st.clear();
		memset(instack,0,sizeof(instack));
		index=0;
		comsum=0;
		memset(belong,0,sizeof(belong));
	}
	void Tarjan(int);
	void Tarjan(void);
	void addedge(int,int);
	int nodn(void);
	int nidn(void);
	void readlist(int);
	void read(void);
	void printside(void){
		cout<<"=========================="<<endl;
		cout<<"边的信息如下:"<<endl;
		int i;
		for(i=1;i<=n;i++){
			cout<<i<<"传给:"<<endl;
			for(int j=0;j<c[i].size();i++) cout<<c[i][j]<<" ";
			cout<<endl;
		}
		cout<<"=========================="<<endl;
	}
};
void GRAPH::Tarjan(int x){
	if(dfn[x]) return;
	dfn[x]=low[x]=++index;
	st.push_back(x);
	instack[x]=true;
	int i,u;
	for(i=0;i<c[x].size();i++){
		u=c[x][i];
		if(!dfn[u]){
			Tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		else if(instack[u]){
			low[x]=min(low[x],dfn[u]);
		}
	}
	if(dfn[x]==low[x]){
		comsum++;
		int temp;
		do{
			temp=st.back();
			belong[temp]=comsum;
			instack[temp]=false;
			st.pop_back();
			if(st.empty()||temp==x) break;
		}while(temp!=x);
	}
}
void GRAPH::Tarjan(void){
	int i;
	for(i=1;i<=n;i++) Tarjan(i);
}
void GRAPH::addedge(int a,int b){
	if(a==b) return;
	c[a].push_back(b);
	ideg[b]++;
	odeg[a]++;
}
int GRAPH::nodn(void){//出度为0的边数
	int i,sum=0;
	for(i=1;i<=n;i++){
		if(odeg[i]==0) sum++;
	}
	return sum;
}
int GRAPH::nidn(void){//入度为0的边数
	int i,sum=0;
	for(i=1;i<=n;i++){
		if(ideg[i]==0) sum++;
	}
	return sum;
}
void GRAPH::readlist(int x){
	int v;
	while(true){
		scanf("%d",&v);
		if(v==0) return;
		addedge(x,v);
	}
}
void GRAPH::read(void){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) readlist(i);
}
void shrink(GRAPH &G1,GRAPH &G2){//G1缩点至G2
	G2.n=G1.comsum;
	int i,j;
	for(i=1;i<=G1.n;i++){
		for(j=0;j<G1.c[i].size();j++){
			G2.addedge(G1.belong[i],G1.belong[G1.c[i][j]]);
		}
	}
}
void work(void){
	GRAPH ori,scc;
	ori.read();
	ori.Tarjan();
	shrink(ori,scc);
	printf("%d\n",scc.nidn());
	if(scc.n==1) printf("0\n");
	else printf("%d\n",max(scc.nidn(),scc.nodn()));
}
int main(){
	freopen("schlnet.in","r",stdin);
	freopen("schlnet.out","w",stdout);
	work();
	return 0;
}