80分求助(要没~_~)
查看原帖
80分求助(要没~_~)
690160
ask_silently楼主2023/5/26 20:28

点2点7WA了

#include <bits/stdc++.h>
using namespace std;
int n,vis[200005],ru[200005],num=1000000000;
vector<int> vt[200005];

void sc(int x){
	vis[x]=-1;
	for(int i=0;i<vt[x].size();i++){
		if(!--ru[vt[x][i]]) sc(vt[x][i]);
	}
}

void dfs(int x,int sum){
	if(vis[x]){
		num=min(num,sum-1);
		return;
	}
	vis[x]=1;
	for(int i=0;i<vt[x].size();i++){
		dfs(vt[x][i],sum+1);
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		ru[x]++;
		vt[i].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(!ru[i]) sc(i);
	}
//	for(int i=1;i<=n;i++){
//		cout<<i<<":"<<vis[i]<<endl;
//	} 
	for(int i=1;i<=n;i++){
		if(!vis[i]) dfs(i,1);
	}
	printf("%d",num);
	return 0;
}
2023/5/26 20:28
加载中...