C. League of Leesins cf1255c (拓扑排序，搜索）

本文主要是介绍C. League of Leesins cf1255c (拓扑排序，搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Bob is an avid fan of the video game “League of Leesins”, and today he celebrates as the League of Leesins World Championship comes to an end!

The tournament consisted of 𝑛 (𝑛≥5) teams around the world. Before the tournament starts, Bob has made a prediction of the rankings of each team, from 1-st to 𝑛-th. After the final, he compared the prediction with the actual result and found out that the 𝑖-th team according to his prediction ended up at the 𝑝𝑖-th position (1≤𝑝𝑖≤𝑛, all 𝑝𝑖 are unique). In other words, 𝑝 is a permutation of 1,2,…,𝑛.

As Bob’s favorite League player is the famous “3ga”, he decided to write down every 3 consecutive elements of the permutation 𝑝. Formally, Bob created an array 𝑞 of 𝑛−2 triples, where 𝑞𝑖=(𝑝𝑖,𝑝𝑖+1,𝑝𝑖+2) for each 1≤𝑖≤𝑛−2. Bob was very proud of his array, so he showed it to his friend Alice.

After learning of Bob’s array, Alice declared that she could retrieve the permutation 𝑝 even if Bob rearranges the elements of 𝑞 and the elements within each triple. Of course, Bob did not believe in such magic, so he did just the same as above to see Alice’s respond.

For example, if 𝑛=5 and 𝑝=[1,4,2,3,5], then the original array 𝑞 will be [(1,4,2),(4,2,3),(2,3,5)]. Bob can then rearrange the numbers within each triple and the positions of the triples to get [(4,3,2),(2,3,5),(4,1,2)]. Note that [(1,4,2),(4,2,2),(3,3,5)] is not a valid rearrangement of 𝑞, as Bob is not allowed to swap numbers belong to different triples.

As Alice’s friend, you know for sure that Alice was just trying to show off, so you decided to save her some face by giving her any permutation 𝑝 that is consistent with the array 𝑞 she was given.

Input
The first line contains a single integer 𝑛 (5≤𝑛≤105) — the size of permutation 𝑝.

The 𝑖-th of the next 𝑛−2 lines contains 3 integers 𝑞𝑖,1, 𝑞𝑖,2, 𝑞𝑖,3 (1≤𝑞𝑖,𝑗≤𝑛) — the elements of the 𝑖-th triple of the rearranged (shuffled) array 𝑞𝑖, in random order. Remember, that the numbers within each triple can be rearranged and also the positions of the triples can be rearranged.

It is guaranteed that there is at least one permutation 𝑝 that is consistent with the input.

Output
Print 𝑛 distinct integers 𝑝1,𝑝2,…,𝑝𝑛 (1≤𝑝𝑖≤𝑛) such that 𝑝 is consistent with array 𝑞.

If there are multiple answers, print any.

Example
inputCopy
5
4 3 2
2 3 5
4 1 2
outputCopy
1 4 2 3 5

题意： 给出一个排列，每连续3个数取一次，并且3个数的顺序都可以改变和每3个数的排列顺序。
思路： 就是拓扑排序。3个点组在一起，就是连接在了一起，每个点入度加1.每次取入度为1的点输出（有2个，取一个就可以了），并把所连的点度数减一。但是我没想到topo，用了搜索，麻烦了很多，但是效果是一样的。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>using namespace std;typedef long long ll;const int maxn = 1e5 + 7;vector<int>a[maxn]; //第i个三元组对应的数
vector<int>G[maxn]; //i这个数对应的三元组
vector<int>ans;
int vis[maxn],num[maxn],last[10];
int n;void del(int x,int y) { //删除x对应的第y个三元组vector<int>res;for(int i = 0;i < G[x].size();i++) {if(G[x][i] == y) continue;res.push_back(G[x][i]);}G[x] = res;
}void dfs(int now,int sum) {if(sum >= n - 2) return;ans.push_back(now);int cnt = G[now][0];int nex = 0;for(int i = 0;i < a[cnt].size();i++) {int v = a[cnt][i];if(v == now) continue;del(v,cnt);if(G[v].size() == 1) nex = v;}dfs(nex,sum + 1);
}int main() {scanf("%d",&n);for(int i = 1;i <= n - 2;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);a[i].push_back(x);a[i].push_back(y);a[i].push_back(z);G[x].push_back(i);G[y].push_back(i);G[z].push_back(i);}int sta = 0;for(int i = 1;i <= n;i++) {num[i] = G[i].size();}for(int i = 1;i <= n;i++) {if(G[i].size() == 1) {sta = i;break;}}dfs(sta,1);for(int i = 0;i < ans.size();i++) {vis[ans[i]] = 1;printf("%d ",ans[i]);}for(int i = 1;i <= n;i++) {if(!vis[i]) {if(num[i] == 3) {last[1] = i;}else if(num[i] == 2) {last[2] = i;}else last[3] = i;}}printf("%d %d %d\n",last[1],last[2],last[3]);return 0;
}

这是topo排序的算法，两个入边算一度。
则实际的度数是 1 2 3 3…3 3 2 1
我们把最后的2和1都算成3，因为最后一个点有两个入边，倒数第二个点也只会算到两个入边（倒数第三个点和倒数第四个点的入边）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;const int maxn = 2e5 + 7;int head[maxn],nex[maxn * 6],to[maxn * 6],tot;
int deg[maxn],vis[maxn];
vector<int>ans;void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void topo(int sta) {queue<int>q;q.push(sta);vis[sta] = 1;while(!q.empty()) {int now = q.front();q.pop();ans.push_back(now);for(int i = head[now];i;i = nex[i]) {int v = to[i];if(vis[v]) continue;deg[v]--;if(deg[v] == 1) {q.push(v);vis[v] = 1;}}}
}int main() {int n;scanf("%d",&n);for(int i = 1;i <= n - 2;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);deg[x]++;deg[y]++;deg[z]++;add(x,y);add(y,x);add(x,z);add(z,x);add(y,z);add(z,y);}int sta = 0;for(int i = 1;i <= n;i++) {if(deg[i] == 1) {sta = i;break;}}for(int i = 1;i <= n;i++) {if(deg[i] == 1 && i != sta) {deg[i] = 3;for(int j = head[i];j;j = nex[j]) {int v = to[j];if(deg[v] == 2) {deg[v] = 3;}}}}topo(sta);for(int i = 0;i < ans.size();i++) {printf("%d ",ans[i]);}return 0;
}