有一个排列。有\(m\)个三元组\((a_i,b_i,c_i)\)，表示\(b_i\)的位置在\(a_i\)的位置和\(c_i\)的位置之间（不确定\(a_i\)和\(c_i\)的位置关系），满足这个排列。
你现在需要尽可能地还原这个排列，使得有至少一半的三元组被满足。
\(n,m\le 10^5\)
做不出来的神仙构造。。
首先整一个类似于拓扑序的东西，使得\(a_i\)和\(c_i\)一定不同时出现在\(b_i\)前。因为一定有解，所以这个序一定存在。
从后往前扫，构造答案序列。对于一个三元组，在最前面一个位置（即扫到的最后一个位置）统计贡献。设这个位置上的是\(a\)，三元组\((a,b,c)\)可能存在答案序列中\(b\)在\(c\)前和\(b\)在\(c\)后两种情况，可以算出\(a\)放最左边的贡献和最右边的贡献。贪心决定取哪边，并且将\(a\)丢到那一边。
由于贪心地取，所以每次至少一半被满足。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#define N 100005
int n,m;
struct EDGE{
int b,c;
EDGE *las;
} e[N*2];
int ne;
EDGE *last[N];
int in[N],vis[N];
int q[N],t[N];
void init(){
int head=1,tail=0;
for (int i=1;i<=n;++i)
if (!in[i])
q[++tail]=i;
while (head<=tail){
int a=q[head++];
vis[a]=1;
for (EDGE *ei=last[a];ei;ei=ei->las)
if (!vis[ei->c]){
if (!--in[ei->b])
q[++tail]=ei->b;
}
}
for (int i=1;i<=n;++i)
t[q[i]]=i;
}
int _ans[N*2],*ans=_ans+N,l,r,w[N];
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[ne]={b,c,last[a]};
last[a]=e+ne++;
e[ne]={b,a,last[c]};
last[c]=e+ne++;
in[b]++;
}
init();
ans[l=r=0]=q[n];
w[q[n]]=l;
for (int i=n-1;i>=1;--i){
int a=q[i],mn=0,mx=0;
for (EDGE *ei=last[a];ei;ei=ei->las)
if (t[ei->c]>t[a]){
if (w[ei->b]<w[ei->c])
mn++;
else
mx++;
}
if (mn>mx){
ans[--l]=a;
w[a]=l;
}
else{
ans[++r]=a;
w[a]=r;
}
}
for (int i=l;i<=r;++i)
printf("%d ",ans[i]);
return 0;
}