一笔画问题:
输入点数 边数 $1 < = n,m <= 10^5$
输入m
条边
输入起始点
若不构成欧拉回路则输出NO
若构成欧拉回路则输出路径
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
bool used[N];
int h[N], e[N], ne[N], idx;
int ans[N];
int din[N], dout[N];
int cnt;
int n, 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;) {
if(used[i]) {
h[u] = ne[i];
continue;
}
used[i] = true;
used[i ^ 1] = true;
int t = e[i];
i = ne[i];
dfs(t);
ans[++ cnt] = t;
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 0; i < m; i ++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
din[b] ++, dout[a] ++;
}
for(int i = 1; i <= n; i ++) {
if(din[i] + dout[i] & 1) {
puts("NO");
return 0;
}
}
int start;
cin >> start;
dfs(start);
if(cnt < m) puts("NO");
else {
cout << start << endl;
for(int i = cnt; i; i --) cout << ans[i] << endl;
}
return 0;
}