求助40pts
查看原帖
求助40pts
158878
B1ade_楼主2021/12/15 13:17

请忽略MLE

WA了,找不到哪里错了

#include<bits/stdc++.h>
using namespace std;
int f[5001][5001];
int slc[5001];
int low[5001],dfn[5001];

stack<int>s;
bool instack[5001];
int tar[5001][5001];
int qltfldx[5001];
map<int,bool>mope[5001];
bool ifchecked[5001];

int n,m,t=0,tot=0;

void dfs(int a)
{
	ifchecked[a]=1;
	s.push(a);
	instack[a]=1;
	dfn[a]=++t;
	low[a]=dfn[a];
	for (int i=1;i<=slc[a];++i)
	{
		int k=f[a][i];
		if (!instack[k]&&!ifchecked[k])
		{
			dfs(k);
		}
		if (instack[k]&&low[k]<low[a]) low[a]=low[k];
	}
	if (low[a]==dfn[a])
	{
		++tot;
		while (s.size()&&low[s.top()]==dfn[a])
		{
			int op=s.top();
			instack[op]=0;
			s.pop();
			mope[tot][op]=1;
			tar[tot][++qltfldx[tot]]=op;
		}
	}
}
int main()
{
//	freopen("op.txt","r",stdin);
	cin>>n>>m;
	memset(ifchecked,0,sizeof(0));
	for (int i=1;i<=m;++i)
	{
		int u,v;cin>>u>>v;
		f[u][++slc[u]]=v;
	}
	dfs(1);
	bool fff=0;
	int sopz;
	for (int i=1;i<=tot;++i)
	{
		bool tf=0;
		for (int j=1;j<=qltfldx[i];++j)
		{
			for (int p=1;p<=slc[tar[i][j]];++p)
			{
				if (!mope[i][f[tar[i][j]][p]])
				{
					tf=1;
					break;
				}
			}
			if (tf) break;
		}
		if (!tf&&!fff)
		{
			fff=1;
			sopz=qltfldx[i];
		}
		else
		if (!tf&&fff)
		{
			cout<<0;
			return 0;
		}
	}
//	for (int i=1;i<=n;++i) cout<<low[i]<<' ';
//	cout<<n;
	if (fff) cout<<sopz;
	else cout<<0;
	return 0;
}
2021/12/15 13:17
加载中...