洛谷能过,交vjudge poj却寄了!蒟蒻不懂
查看原帖
洛谷能过,交vjudge poj却寄了!蒟蒻不懂
674104
Light_Tea楼主2023/1/23 16:33
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
#include<vector>
#define int long long
#define maxn 105
using namespace std;

int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

vector <int> g[105];
int dfn[105],low[105],cnt=0;
bool vis[105],inz[105];
int tot=0,belong[105],num[105];
int in[105],out[105];
stack <int> st;
int n;

void init(){
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	for(int i=0;i<105;i++){
		g[i].clear();
		vis[i]=0,inz[i]=0;
	}
	tot=0;cnt=0;
	memset(belong,0,sizeof(belong));
	memset(num,0,sizeof(num));
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	while(!st.empty()) st.pop();
}

void tarjan(int rt){
	dfn[rt]=++cnt;low[rt]=dfn[rt];
	st.push(rt);
	inz[rt]=1;vis[rt]=1;
	for(int j=0;j<g[rt].size();j++){
		int to=g[rt][j];
		if(!vis[to]){
			tarjan(to);
			low[rt]=min(low[rt],low[to]);
		}else if(inz[to]){
			low[rt]=min(low[rt],dfn[to]);
		}
	}
	if(dfn[rt]==low[rt]){
		tot++;
		int now;
		do{
			now=st.top();st.pop();
			inz[now]=0;
			belong[now]=tot;
			num[tot]++;
		}while(now!=rt);
	}
	return ;
}

signed main()
{
	while(scanf("%lld",&n)!=EOF){
	init();
	int x=-1;
	for(int i=1;i<=n;i++){
		while(1){
			x=read();
			if(!x) break;
			g[i].push_back(x);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]) tarjan(i);
	}
	for(int rt=1;rt<=n;rt++){
		for(int j=0;j<g[rt].size();j++){
			int to=g[rt][j];
			if(belong[rt]==belong[to]) continue;
			in[belong[to]]++;
			out[belong[rt]]++;
		}
	}
	int ct1=0,ct2=0;
	for(int i=1;i<=tot;i++){
		if(!in[i]) ct1++;
		if(!out[i]) ct2++;
	}
	if(tot==1){
		printf("1\n0");
	}else{
		printf("%lld\n%lld",ct1,max(ct1,ct2));	
	}
	}
	return 0;
}
2023/1/23 16:33
加载中...