P7771 欧拉路径

题面

这里不放题面了，扔个链接。

题意就是找一条字典序最小的欧拉路径（或欧拉回路）。

思路

有向图中找欧拉路径相信大家都会，就是不断递归删边然后回溯的时候将起点压栈就可以了。

然后如何做到字典序最小呢？

我们可以先将图建出来，然后遍历每个点的出边，把每个点的出边按照字典序从小到大排序，这样遍历的时候就可以实现字典序最小了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10000005,M=20000005;
int frt[N],nxt[M],to[M],cnt,now[N];
int rd[N],cd[N];
int flg;
int S,T,top;
int stk[M];
void add_edge(int u,int v)
{
	cnt++;
	nxt[cnt]=frt[u];
	rd[v]++;
	cd[u]++;
	frt[u]=cnt;
	to[cnt]=v;
	return;
}
int a[M];
bool cmp(int u,int v)//见过鄙视你按字典序升序排序
{
	return to[u]<to[v];
}
void readd(int u)
{
	int tot=0;
	for(int i=frt[u];i;i=nxt[i]) a[++tot]=i;//将每条边的编号记录在a数组，然后排序后重新建边
	sort(a+1,a+1+tot,cmp);
	frt[u]=0;//现在以u为起点的边都被拆完排好序了
	for(int i=tot;i>=1;i--)
	{
		nxt[a[i]]=frt[u];//从最大的边开始倒着往前建，不断往前加边
		frt[u]=a[i];//第一条边就变成了a[i] 
	}
	return;
}
void dfs(int u)
{
	for(;now[u];)//now[]代表当前所在的边
	{
		int v=to[now[u]];
		now[u]=nxt[now[u]];//先把它去掉 
		dfs(v);
	}
	stk[++top]=u;
	return;
}
signed main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
	}
	for(int i=1;i<=n;i++)
	{
		readd(i);//重新建边 
		now[i]=frt[i];//重新建边后一开始在看最小的一条边
	}
	for(int i=1;i<=n;i++)
	{
		if(cd[i]>rd[i])//起点 
		{
			if(cd[i]!=rd[i]+1) flg=1;//出度不比入度多1，不合法
			else
			{
				if(S) flg=1;//有多个起点，不合法
				else S=i;//否则就作为起点
			}
		}
		if(rd[i]>cd[i])//终点 
		{
			if(rd[i]!=cd[i]+1) flg=1;//入度不比出度多1，那就不是终点，不合法
			else
			{
				if(T) flg=1;//有多个终点，不合法
				else T=i;//否则就作为终点
			}
		}
	}
	if(flg||!S&&T||!T&&S)//若不合法或者没有起点或者没有终点
	{
		puts("No");
		return 0;
	}
	if(!S) S=1;//如果起点终点都没有，说明每个点的入度都等于出度，那么就可以找欧拉回路，将起点定为1.
	dfs(S);
	for(int i=top;i>=1;i--)
		printf("%d ",stk[i]);
	return 0;
}