链式前向星TLE最后一个点,求助
查看原帖
链式前向星TLE最后一个点,求助
280604
DiDi123楼主2022/9/29 19:12

rt

#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000001
struct node
{
	int a1,a2;
}ed[MAXN];
bool cmp(node x,node y)
{
	if(x.a1==y.a1) return x.a2>y.a2;
	return x.a1>y.a1;
}
struct edge
{
	int to,nex;
}Edge[MAXN];
int head[MAXN],cnt,sum;
int od[MAXN],ind[MAXN],vis[MAXN];
void add(int u,int v)
{
	Edge[cnt].nex=head[u];
	Edge[cnt].to=v;
	head[u]=cnt++;
	od[u]++,ind[v]++;
}
int n,m,start=1;
bool f1=false,f2=false;
stack <int> ss;
void dfs(int st)
{
	if(od[st])
	{
		for(int i=head[st];i!=-1;i=Edge[i].nex)
		{
			if(vis[i]) continue;
			vis[i]=1;
			head[st]=Edge[i].nex;
			od[st]--;
			dfs(Edge[i].to);
		}
	}
	
	ss.push(st);
}
inline int read()
{
	int x=0;
	char ch=getchar();
	while(ch>'9' || ch<'0') ch=getchar();
	while(ch>='0' && ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}
int main()
{
	n=read(),m=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
		ed[i].a1=read(),ed[i].a2=read();
	sort(ed+1,ed+1+m,cmp);
	for(int i=1;i<=m;i++)
		add(ed[i].a1,ed[i].a2);
	for(int i=n;i>=1;i--)
		if(od[i]!=ind[i])
		{
			if(od[i]>ind[i])
			{
				if(f1 || od[i]-ind[i]>1) 
				{
					cout<<"No";
					return 0;
				}
				else f1=true;
			}
			else if(ind[i]>od[i])
			{
				if(f2 || ind[i]-od[i]>1) 
				{
					cout<<"No";
					return 0;
				}
				else f2=true;
			}
			
			start=i;
		}
	dfs(start);
	while(ss.size())
	{
		cout<<ss.top()<<' ';
		ss.pop();
	}
}
2022/9/29 19:12
加载中...