求优化(TLE)
查看原帖
求优化(TLE)
1053119
hard_learn楼主2024/4/12 18:08
#include<bits/stdc++.h>
using namespace std;
int n;
int ans=1;
int sum=INT_MAX; 
bool flag[200005];
vector<int> a[200005];
void dfs(int j,int x,int &ans){
	if(flag[x]==1){
		return;
	}
	flag[x]=1;
	for(int i=0;i<a[x].size();i++){
		if(flag[a[x][i]]==0){
			ans++;
			dfs(j,a[x][i],ans);
		}
		else if(a[x][i]==j){
			sum=min(sum,ans);
			ans=0;
			return ;
		}
		else if(flag[a[x][i]]==1){
			return ;
		}
	}
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int t;
		cin>>t;
		a[i].push_back(t); 
	}
	for(int i=1;i<=n;i++){
		dfs(i,i,ans);
		memset(flag,0,sizeof(flag));
	}
	cout<<sum+1<<endl;
    return 0;
}
2024/4/12 18:08
加载中...