|
|
/*
|
|
|
https://codeforces.com/problemset/problem/36/E
|
|
|
欧拉路+并查集+思路~
|
|
|
|
|
|
简直要被绕晕了……有好多细节要注意……
|
|
|
|
|
|
首先，要分为只有一个联通块，有一个联通块和有两个及以上联通块，判断联通块数用并查集。
|
|
|
|
|
|
最后一种是不行的，直接输出-1。
|
|
|
|
|
|
对于其余两种，要判断每个点的入度是否满足欧拉路条件（没有奇点或有两个奇点），特别的，对于第二种，
|
|
|
每个连通块内要分别判断。
|
|
|
|
|
|
然后，如果有两个奇点，从其中一个出发遍历即可。
|
|
|
|
|
|
在第一种情况中，如果有0个或2个起点，则求出总的欧拉路后从任意处截断。
|
|
|
|
|
|
如果有4个起点，任选两个连边后求欧拉路，再在连的边处截断。
|
|
|
|
|
|
https://blog.csdn.net/xianpingping/article/details/82468730
|
|
|
|
|
|
*/
|
|
|
#include <cstdio>
|
|
|
#include <cstring>
|
|
|
#include <iostream>
|
|
|
#include <algorithm>
|
|
|
#define M 10100
|
|
|
using namespace std;
|
|
|
struct abcd {
|
|
|
int to, num, next;
|
|
|
bool flag;
|
|
|
} table[M << 1];
|
|
|
int head[M], tot = 1;
|
|
|
int n = 10000, m, a[2], degree[M];
|
|
|
int stack[M], top;
|
|
|
void Add(int x, int y, int z) {
|
|
|
degree[y]++;
|
|
|
table[++tot].to = y;
|
|
|
table[tot].num = z;
|
|
|
table[tot].next = head[x];
|
|
|
head[x] = tot;
|
|
|
}
|
|
|
namespace Union_Find_Set {
|
|
|
int fa[M], rank[M];
|
|
|
int Find(int x) {
|
|
|
if (!fa[x] || fa[x] == x)
|
|
|
return fa[x] = x;
|
|
|
return fa[x] = Find(fa[x]);
|
|
|
}
|
|
|
void Union(int x, int y) {
|
|
|
x = Find(x);
|
|
|
y = Find(y);
|
|
|
if (x == y) return;
|
|
|
if (rank[x] > rank[y])
|
|
|
swap(x, y);
|
|
|
if (rank[x] == rank[y])
|
|
|
rank[y]++;
|
|
|
fa[x] = y;
|
|
|
}
|
|
|
} // namespace Union_Find_Set
|
|
|
void DFS(int x) {
|
|
|
int i;
|
|
|
for (i = head[x]; i; i = head[x]) {
|
|
|
head[x] = table[head[x]].next;
|
|
|
if (table[i].flag)
|
|
|
continue;
|
|
|
table[i ^ 1].flag = true;
|
|
|
DFS(table[i].to);
|
|
|
stack[++top] = table[i].num;
|
|
|
}
|
|
|
}
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("CF36E.in", "r", stdin);
|
|
|
#endif
|
|
|
using namespace Union_Find_Set;
|
|
|
int i, x, y;
|
|
|
cin >> m;
|
|
|
if (m == 1) {
|
|
|
cout << -1 << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
for (i = 1; i <= m; i++) {
|
|
|
scanf("%d%d", &x, &y);
|
|
|
Add(x, y, i);
|
|
|
Add(y, x, i);
|
|
|
Union(x, y);
|
|
|
}
|
|
|
for (i = 1; i <= n; i++)
|
|
|
if (head[i]) {
|
|
|
if (!a[0])
|
|
|
a[0] = i;
|
|
|
else if (Find(i) != Find(a[0])) {
|
|
|
if (!a[1])
|
|
|
a[1] = i;
|
|
|
else if (Find(i) != Find(a[1]))
|
|
|
return cout << -1 << endl, 0;
|
|
|
}
|
|
|
}
|
|
|
if (a[1]) {
|
|
|
int cnt[2] = {0, 0};
|
|
|
int st[2] = {a[0], a[1]};
|
|
|
for (i = 1; i <= n; i++)
|
|
|
if (degree[i] & 1) {
|
|
|
cnt[Find(i) == Find(a[1])]++;
|
|
|
st[Find(i) == Find(a[1])] = i;
|
|
|
}
|
|
|
if (cnt[0] > 2 || cnt[1] > 2)
|
|
|
return cout << -1 << endl, 0;
|
|
|
DFS(st[0]);
|
|
|
cout << top << endl;
|
|
|
while (top)
|
|
|
printf("%d%c", stack[top], top == 1 ? '\n' : ' '), top--;
|
|
|
DFS(st[1]);
|
|
|
cout << top << endl;
|
|
|
while (top)
|
|
|
printf("%d%c", stack[top], top == 1 ? '\n' : ' '), top--;
|
|
|
} else {
|
|
|
int st[4] = {0, 0, 0, 0};
|
|
|
for (i = 1; i <= n; i++)
|
|
|
if (degree[i] & 1) {
|
|
|
if (!st[0])
|
|
|
st[0] = i;
|
|
|
else if (!st[1])
|
|
|
st[1] = i;
|
|
|
else if (!st[2])
|
|
|
st[2] = i;
|
|
|
else if (!st[3])
|
|
|
st[3] = i;
|
|
|
else
|
|
|
return cout << -1 << endl, 0;
|
|
|
}
|
|
|
if (!st[0]) {
|
|
|
DFS(a[0]);
|
|
|
cout << 1 << '\n'
|
|
|
<< stack[top--] << endl;
|
|
|
cout << top << endl;
|
|
|
while (top)
|
|
|
printf("%d%c", stack[top], top == 1 ? '\n' : ' '), top--;
|
|
|
} else if (!st[2]) {
|
|
|
DFS(st[0]);
|
|
|
cout << 1 << '\n'
|
|
|
<< stack[top--] << endl;
|
|
|
cout << top << endl;
|
|
|
while (top)
|
|
|
printf("%d%c", stack[top], top == 1 ? '\n' : ' '), top--;
|
|
|
} else {
|
|
|
Add(st[0], st[1], m + 1);
|
|
|
Add(st[1], st[0], m + 1);
|
|
|
DFS(st[2]);
|
|
|
for (i = 1; i <= top; i++)
|
|
|
if (stack[i] == m + 1)
|
|
|
break;
|
|
|
cout << top - i << endl;
|
|
|
while (top > i)
|
|
|
printf("%d%c", stack[top], top == i + 1 ? '\n' : ' '), top--;
|
|
|
top--;
|
|
|
cout << top << endl;
|
|
|
while (top)
|
|
|
printf("%d%c", stack[top], top == 1 ? '\n' : ' '), top--;
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
} |
