玄关,tarjan求调qwq
查看原帖
玄关,tarjan求调qwq
511811
崛起的滑稽楼主2024/8/22 20:00

样例过不去的,输出1424(ans初始值)

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=1e4+10;
int n,m,low[MAXN],dfn[MAXN],idx;
vector<int> a[MAXN];
stack<int> nodes;
int A[MAXN],C,B[MAXN],out[MAXN];
bool instack[MAXN];
void tarjan(int x){
	nodes.push(x);
	low[x]=dfn[x]=++idx;
	instack[x]=true;
	for(int v:a[x]){
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(instack[v]){
			low[x]=min(low[x],dfn[v]);
		}
	}
	if(dfn[x]==low[x]){
		++C;
		while(nodes.top()!=x){
			++A[C];
			B[nodes.top()]=C;
			instack[nodes.top()]=false;
			nodes.pop();
		}
		++A[C];
		B[nodes.top()]=C;
		instack[nodes.top()]=false;
		nodes.pop();
	}
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>m;
	for(int i=1;i<=m;++i){
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=n;++i){
		for(int v:a[i]){
			if(B[i]!=B[v]){
				++out[B[i]];
			}
		}
	}
	bool haveAns=false;
	int ans=1424;
	for(int i=1;i<=C;++i){
		if(!out[i]){
			if(haveAns){
				cout<<0<<endl;
				return 0;
			}
			haveAns=true;
			ans=A[i];
		}
	}
	cout<<ans;
	return 0;
}
2024/8/22 20:00
加载中...