AcWing 6099. 座位

原题目链接

问题描述

有 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