欧拉回路 模版dfs stack两种版本

stack堆栈代替dfs版本

// 欧拉模版.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
* https://loj.ac/p/10105
有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

这张图是无向图。（50 分）

这张图是有向图。（50 分）

输入格式
第一行一个整数 t，表示子任务编号。t \in \{1, 2\}，如果 t = 1 则表示处理无向图的情况，如果 t = 2 则表示处理有向图的情况。

第二行两个整数 n, m，表示图的结点数和边数。

接下来 m 行中，第 i 行两个整数 v_i, u_i，表示第 i 条边（从 1 开始编号）。保证 1 \leq v_i, u_i \leq n。

如果 t = 1 则表示 v_i 到 u_i 有一条无向边。

如果 t = 2 则表示 v_i 到 u_i 有一条有向边。

图中可能有重边也可能有自环。

输出格式
如果不可以一笔画，输出一行 NO。

否则，输出一行 YES，接下来一行输出一组方案。

如果 t = 1，输出 m 个整数 p_1, p_2, ~~~~~~, p_m。令 e = \lvert p_i \rvert，那么 e 表示经过的第 i 条边的编号。如果 p_i 为正数表示从 v_e 走到 u_e，否则表示从 u_e 走到 v_e。

如果 t = 2，输出 m 个整数 p_1, p_2, ~~~~~~, p_m。其中 p_i 表示经过的第 i 条边的编号。


1
3 3
1 2
2 3
1 3

YES
1 2 -3



2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

YES
4 1 3 5 2 6


数据范围与提示
1<=n<=10^5 0<=m<=2*10^5
*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

const int N = 100010, M = 400010;
int h[N], e[M], ne[M], idx;
int n, m; int type;
int din[N], dout[N];
int cnt; int ans[M];
int used[M];
bool vis[M];
int stack_[M];
int top;
deque<int> st;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void euler(int u) {
	stack_[++top] = u;
	while (top > 0) {
		int x = stack_[top], i = h[x];
		while (i!=-1 && vis[i]) i = ne[i];
		if (i != -1) {
			stack_[++top] = e[i];
			h[x] = ne[i];
			vis[i] = true;
			if (type == 1) {
				vis[i ^ 1] = true;
			}

			if (type == 1) {
				int idx = i / 2 + 1;
				if (i % 2 == 1) idx = -idx;
				st.push_back(idx);
			}
			else {
				st.push_back(i+1);
			}
		}
		else {
			top--;
			if (!st.empty())
			{
				ans[++cnt] = st.back(); st.pop_back();
			}
		}
	}
}


int main() {
	scanf("%d", &type);
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);

	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b); dout[a]++; din[b]++;
		if (type == 1) { add(b, a); }
	}

	if (type == 1) {
		for (int i = 1; i <= n; i++) {
			if ((din[i] + dout[i]) % 2 != 0) {
				cout << "NO" << endl; return 0;
			}
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (din[i] != dout[i]) {
				cout << "NO" << endl; return 0;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (h[i] != -1) {
			euler(i); break;
		}
	}

	if (cnt != m) {
		cout << "NO" << endl; return 0;
	}

	cout << "YES" << endl;
	for (int i = cnt; i; i--) printf("%d ", ans[i]);
	cout << endl;


	return 0;
}

dfs版本

// 欧拉模版.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
* https://loj.ac/p/10105
有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

这张图是无向图。（50 分）

这张图是有向图。（50 分）

输入格式
第一行一个整数 t，表示子任务编号。t \in \{1, 2\}，如果 t = 1 则表示处理无向图的情况，如果 t = 2 则表示处理有向图的情况。

第二行两个整数 n, m，表示图的结点数和边数。

接下来 m 行中，第 i 行两个整数 v_i, u_i，表示第 i 条边（从 1 开始编号）。保证 1 \leq v_i, u_i \leq n。

如果 t = 1 则表示 v_i 到 u_i 有一条无向边。

如果 t = 2 则表示 v_i 到 u_i 有一条有向边。

图中可能有重边也可能有自环。

输出格式
如果不可以一笔画，输出一行 NO。

否则，输出一行 YES，接下来一行输出一组方案。

如果 t = 1，输出 m 个整数 p_1, p_2, ~~~~~~, p_m。令 e = \lvert p_i \rvert，那么 e 表示经过的第 i 条边的编号。如果 p_i 为正数表示从 v_e 走到 u_e，否则表示从 u_e 走到 v_e。

如果 t = 2，输出 m 个整数 p_1, p_2, ~~~~~~, p_m。其中 p_i 表示经过的第 i 条边的编号。


1
3 3
1 2
2 3
1 3

YES
1 2 -3



2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

YES
4 1 3 5 2 6


数据范围与提示
1<=n<=10^5 0<=m<=2*10^5
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 400010;
int h[N], e[M], ne[M], idx;
int n, m; int type;
int din[N], dout[N];
int cnt; int ans[M];
int used[M];


void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
	for (int& i = h[u]; i != -1; ) {
		if (used[i]) {
			i = ne[i];
			continue;
		}
		used[i] = 1;
		if (type == 1) used[i ^ 1] = true;
		int t;
		if (type == 1) {
			t = i / 2 + 1;
			if (i % 2 == 1) { t = -t; }
		}
		else {
			t = i + 1;
		}
		int j = e[i];
		i = ne[i];
		dfs(j);

		ans[++cnt] = t;
	}
}


int main()
{
	scanf("%d",&type);
	scanf("%d%d",&n,&m);
	memset(h, -1, sizeof h);

	for (int i = 0; i < m; i++) {
		int a, b; 
		scanf("%d%d",&a,&b);
		add(a, b); dout[a]++; din[b]++;
		if (type == 1) { add(b, a); }
	}

	if (type == 1) {
		for (int i = 1; i <= n; i++) {
			if ((din[i] + dout[i]) % 2 != 0) {
				cout << "NO" << endl; return 0;
			}
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (din[i] != dout[i]) {
				cout << "NO" << endl; return 0;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (h[i] != -1) {
			dfs(i); break;
		}
	}
	if (cnt != m) {
		cout << "NO" << endl; return 0;
	}

	cout << "YES" << endl;
	for (int i = cnt; i; i--) printf("%d ",ans[i]);
	cout << endl;

	return 0;
}