Network of Schools

The first line contains an integer N: the number of schools in the network $(2 \leq N \leq 100)$ . The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 504K, 提交时间: 2020-10-13 17:53:37

#include<cstdio>
#include<stack>
using namespace std;
const int nn=101;
bool in[nn],ou[nn],net[nn][nn];
int n,num,oum,tot,c[nn],dfn[nn],low[nn];
stack<int>st;
void tarjan(int u){
	low[u]=dfn[u]=++num;
	in[u]=true,st.push(u);
	for(int i=1;i<=n;i++)
		if(net[u][i]){
			if(dfn[i]){
				if(in[i])low[u]=min(low[u],dfn[i]);
			}else tarjan(i),low[u]=min(low[u],low[i]);
		}if(dfn[u]==low[u]){
			c[u]=++tot,in[u]=false;
			for(;st.top()!=u;st.pop()){
				c[st.top()]=tot;
				in[st.top()]=false;
			}st.pop();
		}
}int main(){
	scanf("%d",&n);
	for(int i=1,a;i<=n;i++){
		while(scanf("%d",&a)!=EOF){
			if(a==0)break;
			net[i][a]=true;
		}
	}for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	num=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(net[i][j]&&c[i]!=c[j])
				ou[c[i]]=true,in[c[j]]=true;
	for(int i=1;i<=tot;i++){
		if(!in[i])num++;
		if(!ou[i])oum++;
	}return printf("%d\n%d\n",num,tot==1?0:max(num,oum)),0;
}

详情