30pts WA求调
查看原帖
30pts WA求调
567494
Baoziawa_int32768楼主2023/6/9 18:18
#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt=0,dfn[200000+10],ans,low[200000+10],ret=10000000,n,a;
vector<int>V[200000+10],SCC[200000+100];
stack<int>S;
void dfs(int u){
	S.push(u);
	dfn[u]=low[u]=++cnt;
	for(int i=0;i<V[u].size();i++){
		int v=V[u][i];
		if(dfn[v]){
			low[u]=min(low[u],dfn[v]);
		}else{
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
		
	}
	if(low[u]==dfn[u]){
		ans++;
		int t;
		do{
			t=S.top();SCC[cnt].push_back(t);S.pop();
		}while(t!=u);
		ret=min((int)SCC[cnt].size(),ret);
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		V[i].push_back(a);
	}
	dfs(1);
	cout<<ret;
}
2023/6/9 18:18
加载中...