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;
}