原題目鏈接

問題描述

有 n 頭奶牛（n ≥ 5），編號為 1 ～ n，按照某種順序圍著一張圓桌坐成一圈。

奶牛之間存在如下的朋友關系：

• 如果兩頭奶牛相鄰，則它們是朋友；
• 如果兩頭奶牛之間只隔著一頭奶牛，它們也是朋友。

例如，如果共有 5 頭奶牛，沿順時針方向按 1～5 的順序就座，則共有如下 10 對朋友關系：

(1,2), (2,3), (3,4), (4,5), (5,1),
(1,3), (2,4), (3,5), (4,1), (5,2)

不難發現，當 n ≥ 5 時，一共會有 2n 對朋友關系。

現在，給定這 2n 對朋友關系，請你輸出一種可能的奶牛就座順序。

---

輸入格式

• 第一行：一個整數 n，表示奶牛的數量。
• 接下來 2n 行：每行包含兩個整數 a?, b?，表示一對給定的朋友關系。

輸入保證同一對朋友關系不會重復給出。

---

輸出格式

• 如果給定的朋友關系存在錯誤，導致無解，則輸出 -1。
• 否則，請輸出任意一頭奶牛作為起點，并沿順時針或逆時針方向輸出一組 n 個奶牛編號，表示一個合法的就座順序。

如果方案不唯一，可以輸出任意一種合理方案。

---

數據范圍

• 前 5 個測試點滿足：5 ≤ n ≤ 10
• 所有測試點滿足：
  • 5 ≤ n ≤ 10?
  • 1 ≤ a?, b? ≤ n
  • a? ≠ b?

---

輸入樣例 1

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

輸出樣例 1

1 2 3 4 5

---

輸入樣例 2

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

輸出樣例 2

1 2 4 5 3 6

c++代碼

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;int n, a, b;
vector<unordered_set<int>> arr;
vector<bool> know;
vector<int> mid, tem;int main() {scanf("%d", &n);arr = vector<unordered_set<int>>(n + 1);for (int i = 0; i < 2 * n; i++) {scanf("%d %d", &a, &b);if (a == b || arr[a].find(b) != arr[a].end() || arr[b].find(a) != arr[b].end()) {printf("-1");return 0;}arr[a].insert(b);arr[b].insert(a);if (a == 1) tem.push_back(b);if (b == 1) tem.push_back(a);}if (tem.size() != 4) {printf("-1");return 0;}sort(tem.begin(), tem.end());do {mid.clear();mid = { tem[0], tem[1], 1, tem[2], tem[3] };if (arr[tem[0]].find(tem[1]) == arr[tem[0]].end()|| arr[tem[1]].find(tem[2]) == arr[tem[1]].end()|| arr[tem[2]].find(tem[3]) == arr[tem[2]].end()) continue;know = vector<bool>(n + 1, false);know[tem[0]] = true, know[tem[1]] = true, know[tem[2]] = true, know[tem[3]] = true, know[1] = true;for (int i = 3; i <= n - 3; i++) {int k, cont = 0;for (int x : arr[mid[i]]) {if (x == mid[i - 1] || x == mid[i - 2] || x == mid[i + 1]) {cont++;continue;}else k = x;}if (cont != 3 || know[k]) break;mid.push_back(k);know[k] = true;}if (mid.size() != n) continue;int i = 0;for (i = 0; i < n; i++) {vector<int> res(4);res[0] = (i + 1) % n, res[1] = (i + 2) % n, res[2] = (i + n - 1) % n, res[3] = (i + n - 2) % n;int j = 0;for (j = 0; j < 4; j++) {if (arr[mid[i]].find(mid[res[j]]) == arr[mid[i]].end()) break;}if (j != 4) break;}if (i != n) continue;for (i = 0; i < n; i++) {printf("%d ", mid[i]);}return 0;} while (next_permutation(tem.begin(), tem.end()));printf("-1");return 0;
}//by wqs