16分求调,谢谢!
查看原帖
16分求调,谢谢!
482730
aSunnyDay楼主2021/7/19 18:35

各位大佬帮忙看一下,谢谢!

#include<bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long ll;
ll n,m,ans=0,dfn[N],low[N],Bcnt[N],cnt=0,cnt2=0;
bool vis[N],ins[N],vis2[N];
vector<ll> to[N],c[N];
stack<ll> s;
void tarjan(ll x,ll fa){
	vis[x]=1,ins[x]=1,s.push(x),dfn[x]=low[x]=++cnt2;
	for(ll i=0,v;i<to[x].size();++i)
		if(!dfn[v=to[x][i]]){tarjan(v,x);low[x]=min(low[x],low[v]);}
		else if(v!=fa){low[x]=min(low[x],dfn[v]);}
	if(dfn[x]!=low[x]) return;
	ll v=0;
	++cnt;
	do{
		v=s.top();
		Bcnt[v]=cnt;
		c[cnt].push_back(v);
		s.pop();
		ins[v]=0;
		if(x==v) break;
	}while(x!=v);
}
void sodian(){
	for(ll i=1;i<=cnt;++i)
		for(ll j=0,x;j<c[i].size();++j){
			x=c[i][j];
			for(ll k=0,v;k<to[x].size();++k)
				vis2[v]=1;
		}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(ll i=1;i<=n;++i) to[i].push_back(i);
	for(ll i=1;i<=m;++i){
		ll x,y;
		cin>>x>>y;
		to[x].push_back(y);
	}
	tarjan(1,0);
	for(ll i=1;i<=n;++i) if(!vis[i]){cout<<0;exit(0);}
	sodian();
	for(ll i=1;i<=cnt;++i)
		if(!vis2[i]){cout<<c[i].size();return 0;}
	cout<<0;
	return 0;
}
2021/7/19 18:35
加载中...