You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
68 lines
1.5 KiB
68 lines
1.5 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
typedef pair<int, int> PII;
|
|
const int N = 1e5 + 10, M = 2e5 + 10;
|
|
vector<PII> g[N];
|
|
int st[M];
|
|
int ans[M], al;
|
|
int din[N], dout[N];
|
|
int op, n, m;
|
|
|
|
// 需要删边优化
|
|
void dfs(int u) {
|
|
while (g[u].size()) {
|
|
PII x = g[u].back();
|
|
g[u].pop_back();
|
|
|
|
int v = x.first, id = x.second, fid = abs(id);
|
|
if (st[fid]) continue;
|
|
st[fid] = 1;
|
|
dfs(v);
|
|
ans[++al] = id; // 记录的是边号
|
|
}
|
|
}
|
|
// 检查是不是存在欧拉回路
|
|
bool check() {
|
|
int start = 1;
|
|
if (op == 2) {
|
|
for (int i = 1; i <= n; i++) {
|
|
if (din[i] != dout[i]) return 0;
|
|
if (din[i]) start = i;
|
|
}
|
|
} else {
|
|
for (int i = 1; i <= n; i++) {
|
|
if ((din[i] + dout[i]) & 1) return 0;
|
|
if (din[i] + dout[i]) start = i;
|
|
}
|
|
}
|
|
// 判连通，找出欧拉回路
|
|
dfs(start);
|
|
if (al < m) return 0;
|
|
|
|
return 1;
|
|
}
|
|
|
|
int main() {
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("UOJ117.in", "r", stdin);
|
|
#endif
|
|
|
|
scanf("%d %d %d", &op, &n, &m);
|
|
for (int i = 1; i <= m; i++) {
|
|
int a, b;
|
|
scanf("%d%d", &a, &b);
|
|
g[a].push_back({b, i}); // 对边点，边号
|
|
if (op == 1) g[b].push_back({a, -i}); // 无向图
|
|
din[b]++, dout[a]++;
|
|
}
|
|
|
|
if (!check()) {
|
|
puts("NO");
|
|
return 0;
|
|
}
|
|
|
|
puts("YES");
|
|
for (int i = al; i; i--) printf("%d ", ans[i]);
|
|
return 0;
|
|
} |