思路

先直接说结论：从任意节点开始 dfs，搜到环直接输出。

证明

首先题目保证一定有解，不难发现此时所有点的度数都为偶数。而我们任意删掉一个环后每个点的度数还是偶数。一直删下去一定能删完。

实现

暴力就是直接爆搜，类似 tarjan，开个 map 记录哪些边被访问过了，会 T。

考虑优化，由于每个边只会被访问一次，所以我们可以每访问一条边就直接删掉。可以用 vector 存边。

• 删除：用 erase 删除，但要注意这条边是否被删了，不然会 RE。

• 找点：可以将点排序，用 lower_bound 快速查找。

• 时间复杂度：你可能会说 erase 不是 $O(n)$ 的吗？是的，但是 STL 是使用 move_backward 移动的，常数很小，绝大多数情况可以套一个 $O(n)$。

代码

直接说有点抽象，可以结合一下代码。跑的还比较快，在最优解第一页。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;

int n, m;

bool vis[maxn];

vector <int> edge[maxn];

stack <int> st;

void dfs(int x) {
	if(vis[x]) {
		while(1) {
			int t = st.top(); st.pop();
			vis[t] = 0;
			if(t == x) break;
			cout << t << " ";
		}
		cout << x << "\n";
	}
	while(edge[x].size()) {
		int to = *edge[x].begin();
		edge[x].erase(edge[x].begin());
		if(edge[to].size()) {
			auto it = lower_bound(edge[to].begin(), edge[to].end(), x);
			if(*it == x) edge[to].erase(it);
		}
		vis[x] = 1, st.push(x);
		dfs(to);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int u, v;
	for(int i = 1; i <= m; i++) {
		cin >> u >> v;
		edge[u].emplace_back(v);
		edge[v].emplace_back(u);
	}
	for(int i = 1; i <= n; i++) sort(edge[i].begin(), edge[i].end());
	dfs(1);
	return 0;
}