求助72pts
查看原帖
求助72pts
467328
BLePb楼主2022/1/26 12:00
#include<bits/stdc++.h>
using namespace std;

#define re register int
const int N=100001;
vector<int>to[N];
int low[N],dfn[N],cnt,sta[N],at[N],top;
int scc[N],sc;
int size[N],du[N];
int n,m;

void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	sta[++top]=u;
	at[u]=1;
	for(re i=0;i<to[u].size();i++)
	{
		int v=to[u][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		sc++;
		while(sta[top]!=u)
		{
			scc[sta[top]]=sc;
			size[sc]++;
			at[sta[top]]=0;
			top--;
		}
		scc[sta[top]]=sc;
		size[sc]++;
		at[sta[top]]=0;
		top--;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	int x,y;
	for(re i=1;i<=m;i++)
	{
		cin>>x>>y;
		to[x].push_back(y);
	}
	for(re i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i);
	for(re i=1;i<=sc;i++)
		for(re j=0;j<to[i].size();i++)
			if(scc[i]!=scc[to[i][j]]) du[scc[to[i][j]]]++;
	int ans=0,u=0;
	for(re i=1;i<=sc;i++)
		if(!du[i]) ans=size[i],u++;
	if(u==1) cout<<ans<<endl;
	else cout<<0<<endl;
	return 0;
}

问题就是WA的那几个点输出的都是0

2022/1/26 12:00
加载中...