萌新刚学OI,0pts请求DEBUG
查看原帖
萌新刚学OI,0pts请求DEBUG
922691
Hisy楼主2024/7/22 10:22
#include<bits/stdc++.h>
#define MAXN 10001
#define MAXM 50005
using namespace std;
struct node{
	int from,to,next;
}edge[MAXM];
int n,cnt,tim,num,head[MAXN],dfn[MAXN],low[MAXN],fa[MAXN],indeg[MAXN],outdeg[MAXN];
bool vis[MAXN];
stack<int> stk;
inline void addedge(int x,int y){
	edge[++cnt].from=x;
	edge[cnt].to=y;
	edge[cnt].next=head[x];
	head[x]=cnt;
}
inline void tarjan(int now){
	low[now]=dfn[now]=++tim;
	stk.push(now);
	vis[now]=true;
	for(int i=head[now];i;i=edge[i].next){
		int to=edge[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}else if(vis[to]){
			low[now]=min(low[now],low[to]);
		}
	} 
	if(dfn[now]==low[now]){
		++num;
		while(true){
			int top=stk.top();
			stk.pop();
			vis[top]=false;
			fa[top]=num;
			if(top==now){
				return;
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		int x;
		while(true){
			scanf("%d",&x);
			if(!x){
				break;
			}
			addedge(i,x);
		}
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=cnt;++i){
		int x=fa[edge[i].from],y=fa[edge[i].to];
		if(x!=y){
			++indeg[y];
			++outdeg[x];
		}
	}
	int in=0,out=0;
	for(int i=1;i<=num;++i){
		if(!indeg[i]){
			++in;
		}
		if(!outdeg[i]){
			++out;
		}
	}
	printf("%d\n%d",in,max(in,out));
	return 0;
}
2024/7/22 10:22
加载中...