CodeForces 1255C:League of Leesins 拓扑排序

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

传送门

题目描述

给出一个排列，每连续3个数取一次，并且3个数的顺序都可以改变和每3个数的排列顺序。

分析

我们会发现，出现在第一个和最后一个的数字，在三元组中也只会出现一次，出现在第二位和倒数第二位的数字，只会出现两次，其余的都会出现三次，所以，我们可以记录每个数字出现的次数，然后每个三元组里面连边，进行拓扑排序即可

需要注意的是，拓扑排序的时候，当入度减为1的时候，会有多个点入队列，那么需要注意哪个点先入呢，应该是初始度数大的先入队列，因为当度数为3的点减到度数1的时候，说明三元组中其余两个点都已经入队了，所以肯定需要优先入队

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int in[N];
vector<int> son[N];
int n;bool cmp(int a,int b){return in[a] > in[b];
} bool find(int x,int y){for(int i = 0;i < son[x].size();i++)if(son[x][i] == y) return false;return true;
}int main(){scanf("%d",&n);for(int i = 1;i <= n - 2;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);in[x]++,in[y]++,in[z]++;if(find(x,y)) son[x].push_back(y);if(find(y,x)) son[y].push_back(x);if(find(x,z)) son[x].push_back(z);if(find(z,x)) son[z].push_back(x);if(find(y,z)) son[y].push_back(z);if(find(z,y)) son[z].push_back(y);}for(int i = 1;i <= n;i++) sort(son[i].begin(), son[i].end(),cmp);int x = 0,y = 0;	for(int i = 1;i <= n;i++){if(in[i] == 1 && !x) x = i;else if((in[i]) == 1){y = i;break;}}queue<int>Q;Q.push(x);while(Q.size()){int t = Q.front();Q.pop();printf("%d ",t);for(int i = 0;i < son[t].size();i++){in[son[t][i]]--;if(in[son[t][i]] == 1) Q.push(son[t][i]);}}printf("%d",y);return 0;
}/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/