Rockdu's Blog

题目背景

浙江省的几所OI强校的神犇发明了一种人工智能，可以AC任何题目，所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空，他们来找你帮助他们。

题目描述

共有n所学校（n<=10000）已知他们实现设计好的网络共m条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机母鸡，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机母鸡都可以使别的学校使用上软件。

输入输出格式

第一行一个整数n。

接下来n行每行有若干个整数，用空格空格隔开。

第i-1行的非零整数x，表示从i到x有一条线路。以0作为结束标志。

第一行一个整数表示问题1的答案。

第二行回答问题2.

输入输出样例

5
2 0
4 0
5 0
1 0
0

2
2

说明

POJ原题。数据扩大了100倍。

        先用tarjan求出强连通块，然后缩点，新图中入度为0的点的数量为第一问答案。

        再求出Max(入度为0的点的个数 ,  出度为0的点的个数)  为第二问答案。

        下面贴一个Tarjan:

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1e4+100;
const int maxm=1e6+100;

struct edge{
	int v,next;
}e[maxm];
int cnt;
int head[maxn];
void adde(int u,int v){
	e[cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt++;
}
int dfn[maxn],low[maxn];
int fa[maxn];
bool vis[maxn];
int indgree[maxn];
int outdgree[maxn];
int idcnt;
int n;

stack<int > stk;
void tarjan(int u){
	dfn[u]=low[u]=++idcnt;
	stk.push(u);
	vis[u]=1;
	for(int i=head[u];i!=-1;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			if(low[v]<low[u])
				low[u]=low[v];
		}else if(vis[v] && dfn[v]<low[u])
			low[u]=dfn[v];
	}
	if(dfn[u]==low[u]){
		int v;
		while(1){
			v=stk.top();
			stk.pop();
			fa[v]=u,vis[v]=0;
			if(v==u) break;
		}
	}
}

int main(){
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	int j=1;
	for(int i=1;i<=n;i++)
		while(1){
			int a;
			scanf("%d",&a);
			if(!a)	break;
			adde(i,a);
		}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;i++){
		for(int j=head[i];j!=-1;j=e[j].next){
			int v=e[j].v;
			if(fa[v]!=fa[i])
				outdgree[i]++,indgree[v]++;
		}
	}
	int odg=0,idg=0;
	for(int i=1;i<=n;i++){
		if(fa[i]!=i) continue;
		if(!outdgree[i])	odg++;
		if(!indgree[i])		idg++;
	}
	printf("%d\n",odg);
	printf("%d",odg>idg?odg:idg);
	return 0;
}