40分求助
查看原帖
40分求助
251775
galiyuebing楼主2023/5/4 10:29

rt,不知道错在哪里

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define pii pair<int,int>
using namespace std;
int n,m,rd[100010],cd[100010],s,t; 
vector<int> edge[100010];
int ans[100010],vis[100010];
void fi(int k)
{
	for(int i=vis[k];i<edge[k].size();i=vis[k])
	{
		vis[k]++;//剪枝优化 
		fi(edge[k][i]);
//		return;
	}
	ans[++ans[0]]=k;
}

int main()
{
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i)
	{
		scanf("%d%d",&u,&v);
		++cd[u];++rd[v];
		edge[u].push_back(v);
	}
	for(int i=1;i<=n;++i)//要求字典序最小,排序 
		sort(edge[i].begin(),edge[i].end());
	for(int i=1;i<=n;++i)
	{
		if(rd[i]!=cd[i])
		{
			if(rd[i]-cd[i]==1 && !t)t=i;//刚刚看题解,发现有向图判断欧拉(回)路是别的条件 
			else if(cd[i]-rd[i]==1 && !s)s=i;
			else {printf("No\n");return 0;}
		}
	}
	if((!s && t) || (s && !t)){printf("No\n");return 0;} 
	fi(s);
	for(int i=ans[0];i>=1;--i)
		printf("%d ",ans[i]);//倒着输出 
	return 0;
}



2023/5/4 10:29
加载中...