P7771 【模板】欧拉路径

网址如下：

P7771 【模板】欧拉路径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

忘掉了输出欧拉回路的方法，搞了我好久

关于欧拉回路的知识可以看我之前的博客：

一点关于欧拉回路的总结-CSDN博客

代码如下：

#include<queue>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;const int maxn = 100001;struct Node{priority_queue<int, vector<int>, greater<int>> q;int indegree, outdegree;Node():indegree(0), outdegree(0){}
}node[maxn];int n;
stack<int> st;int judge(void){int cnt = 0, u = 1;for(int i = 1; i <= n; i++){if(node[i].outdegree != node[i].indegree){cnt++;if(cnt > 2 || abs(node[i].outdegree - node[i].indegree) >= 2) return -1;if(node[i].outdegree - node[i].indegree == 1) u = i;}}return u;
}
void dfs(int u){while(!node[u].q.empty()){int v = node[u].q.top();node[u].q.pop();dfs(v);}st.push(u);
}int main(void)
{int m;//输入scanf("%d%d", &n, &m);while(m--){int u, v;scanf("%d%d", &u, &v);node[u].outdegree++; node[v].indegree++;node[u].q.push(v);}//处理int u = judge();if(u == -1) printf("No");else{dfs(u);while(!st.empty()) printf("%d ",st.top()),st.pop();}return 0;
}

可以看看一开始我写的错误代码（对欧拉回路理解不够深造成的）：

#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;const int maxn = 100001;struct Node{priority_queue<int, vector<int>, greater<int>> q;int indegree, outdegree;Node():indegree(0), outdegree(0){}
}node[maxn];int n;int judge(void){int cnt = 0, u = 1;for(int i = 1; i <= n; i++){if(node[i].outdegree != node[i].indegree){cnt++;if(cnt > 2 || abs(node[i].outdegree - node[i].indegree) >= 2) return -1;if(node[i].outdegree - node[i].indegree == 1) u = i;}}return u;
}int main(void)
{int m;//输入scanf("%d%d", &n, &m);while(m--){int u, v;scanf("%d%d", &u, &v);node[u].outdegree++; node[v].indegree++;node[u].q.push(v);}//处理int u = judge();if(u == -1) printf("No");else{printf("%d", u);while(!node[u].q.empty()){int v = node[u].q.top(); node[u].q.pop();printf(" %d", v);u = v; }}return 0;
}