不知道为什么 完全不对( 求调
查看原帖
不知道为什么 完全不对( 求调
512956
zjt_AKUYTRE楼主2024/7/7 11:32
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int MAXN=500000;
long long h[MAXN],tot=0,n,m,dfn[MAXN],vo[MAXN],num,low[MAXN],vol=0,ru[MAXN],cu[MAXN];
long long answ[MAXN];
stack<long long>s;
struct Node{
	int to,nxt;
}e[MAXN];
void Add(int xx,int yy){
	e[++tot].to=yy;
	e[tot].nxt=h[xx];
	h[xx]=tot;
}
void tarjan(int u){
	dfn[u]=low[u]=++num;
	s.push(u);
	for(int i=h[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!vo[v])
			low[u]=min(low[u],dfn[v]);	
	}
	if(low[u]==dfn[u]){
		vo[u]=++vol;
		while(s.top()!=u){
			vo[s.top()]=vol;
			s.pop();
		}
		s.pop();
	}
}
int main(){
	int ans1=0,ans2=0;
	cin>>n;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=n;i++){
		int x;
		while(x!=0){
			cin>>x;
			m++;
			Add(i,x);
		}
	}
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int u=1;u<=n;u++){
		for(int j=h[u];j!=-1;j=e[j].nxt){
			int v=e[u].to;
			if(vo[u]!=vo[v]){
				ru[vo[v]]++;
				cu[vo[u]]++;
			}
		}	
	}
	for(int i=1;i<=vol;i++){
		if(ru[i]==0)ans1++;
		if(cu[i]==0)ans2++;
	}
	cout<<ans1<<endl;
	if(vol==1)cout<<0<<endl;
	else cout<<max(ans1,ans2)<<endl;
	return 0;
}
2024/7/7 11:32
加载中...