【模板】欧拉路径(有向图输出字典序最小)
思路：
- 坑点：字典序最大反过来找不会是字典序最小
- 欧拉路径是逆序输出的，先遍历的点在数组中位置越后，逆序后就越前
- 只需要按照当前字典序最小的点先走即可，逆序输出即为字典序最小
cpp
int n,m;
vector<int> adj[N];
int del[N],din[N],dout[N],ans[M],cnt;
void dfs(int u){
for(int i=del[u];i<adj[u].size();i=del[u]){
del[u]=i+1;
dfs(adj[u][i]);
ans[++cnt]=adj[u][i];
}
}
void solve(){
cin>>n>>m;
while(m--){
int u,v;
cin>>u>>v;
dout[u]++,din[v]++;
adj[u].push_back(v);
}
for(int i=1;i<=n;i++)sort(adj[i].begin(),adj[i].end());
bool in=0,out=0;
int start=1;
for(int i=1;i<=n;i++){
if(din[i]!=dout[i]){
if(din[i]==dout[i]+1){
if(in){
cout<<"No\n";
return;
}
in=1;
}
else if(dout[i]==din[i]+1){
if(out){
cout<<"No\n";
return;
}
out=1;
start=i;
}
else{
cout<<"No\n";
return;
}
}
}
if(in^out){
cout<<"No\n";
return;
}
dfs(start);
ans[++cnt]=start;
for(int i=cnt;i;i--)cout<<ans[i]<<" ";
}