League of Leesins(拓扑排序)

62 阅读 0 评论 41 点赞

我是靠谱客的博主要减肥水杯，最近开发中收集的这篇文章主要介绍League of Leesins(拓扑排序)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem - 1255C - Codeforces

鲍勃是视频游戏 "Leesins联盟 "的狂热粉丝，今天他庆祝Leesins联盟世界锦标赛的结束

这次比赛由世界各地的n（n≥5）支队伍组成。在比赛开始前，鲍勃对每支球队的排名进行了预测，从第1名到第n名。决赛结束后，他将预测与实际结果进行了比较，发现根据他的预测，第i个球队最终排在了第pi个位置（1≤pi≤n，所有pi都是唯一的）。换句话说，p是1,2,...,n的一个排列组合。

由于鲍勃最喜欢的联盟球员是著名的 "3ga"，他决定写下permutation p的每3个连续元素。形式上，鲍勃创建了一个由n-2个三要素组成的数组q，其中qi=（pi,pi+1,pi+2），每1≤i≤n-2。鲍勃对他的数组非常自豪，所以他向他的朋友爱丽丝展示了它。

在得知鲍勃的数组后，爱丽丝宣称，即使鲍勃重新排列q的元素和每个三联体中的元素，她也能找回排列组合p。当然，鲍勃不相信这样的魔法，所以他就像上面那样做，看看爱丽丝的反应。

例如，如果n=5，p=[1,4,2,3,5]，那么原始数组q将是[(1,4,2), (4,2,3), (2,3,5)]。然后Bob可以重新排列每个三倍体中的数字和三倍体的位置，得到[(4,3,2), (2,3,5), (4,1,2)]。注意[(1,4,2),(4,2,2),(3,3,5)]不是一个有效的q的重排，因为鲍勃不允许把属于不同三联体的数字交换。

作为爱丽丝的朋友，你肯定知道爱丽丝只是想炫耀，所以你决定给她一些面子，给她任何与她所给的数组q一致的排列组合p。

输入
第一行包含一个整数n（5≤n≤105）-- permutation p的大小。

接下来n-2行中的第i行包含3个整数qi,1, qi,2, qi,3 (1≤qi,j≤n) --重新排列（洗牌）的数组qi的第i个三联体的元素，以随机顺序。记住，每个三联体中的数字可以被重新排列，三联体的位置也可以被重新排列。

可以保证至少有一个排列组合p与输入一致。

输出
打印n个不同的整数p1,p2,...,pn(1≤pi≤n)，使得p与数组q一致。

如果有多个答案，打印任何一个。

例子
inputCopy
5
4 3 2
2 3 5
4 1 2
输出拷贝
1 4 2 3 5

我们可以找到这么一个关系，对于给出的三元组中，只出现过一次的数字一定是在原序列中的第一个或者最后一个，只出现过两次的数字只出现在原序列中的第二个或者倒数第二个，中间的数字都出现了三次，那么如果我们从第一个数开始找，将与它处于同一个三元组中的数的出现次数都-1，如果有一个数出现了一次，那么这个是就是这个三元组后面一个三元组的开始元素，但是这种只能处理到前n-2个元素，因为前N-2个元素的出现次数为1,2,3,3,3,3,3…这样的序列，而最后两个元素的出现次数为2,1，当处理到这里的时候，就会出现两个出现次数为1的元素（当减去倒数第二个三元组的所有元素的时候），所以这里我们需要特判一下，然后拓扑排序就可以啦。

#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int n;
const int N = 6e5+10;
vector<int> g[N];
int f[N];
int vis[N];
void add(int a,int b)
{
g[a].push_back(b);
g[b].push_back(a);
}
void topu(int a)
{
queue<int> q;
q.push(a);
vis[a] = 1;
while(q.size())
{
int k = q.front();
printf("%d ",k);
q.pop();
for(auto v:g[k])
{
if(!vis[v])
{
f[v]--;
if(f[v] == 1)
{
vis[v] = 1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d ", &n);
for(int i = 1; i <= n - 2; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b);
add(b,c);
add(a,c);
f[a]++;
f[b]++;
f[c]++;
}
int a = 0 ,b = 0;
for(int i = 1; i <= n; i++)
{
if(f[i] == 1)
{
if(a == 0)
{
a = i;
}
else
{
f[i] = 3;
}
}
}
for(auto v :g[a])
{
if(f[v] == 2)
b = v;
}
for(int i = 1; i <= n ;i ++)
{
if(f[i] == 2&&i != b)
{
f[i] ++;
}
}
topu(a);
}