正解:拓扑排序
解题报告:
首先看到它这个约束就应该要想到拓扑排序辣QwQ
首先想到的应该是用优先队列代替队列,按照节点编号排序
然后也很容易被hack:<5,1> 正解应为5,1,2,3,4 但是上面这个想法的结果是2,3,4,5,1
那就想要不优化一下趴,按照能到达的点为第一关键字,自己点的编号为第二关键字排序呢
还是布星,,,<5,2><5,4><2,1><4,3><3,1> 正解应为5,2,1,4,3,但是上面这个想法的结果是4,3,1,5,2
哦对了,这道题要,仔细理解一下题意,,,并不是要字典序最小的昂(看上面两个都看得出来QwQ)只是要小的数尽量放在前面
所以考虑,反着做
就贪心地想,可以想到大的数尽量放后边,因为大的放得很后面前面就有更多的位置放比较小的数嘛,从后往前安排,每次只考虑最后一位,放上合法的编号最大的数就好了
然后思考怎么样是合法的呢,就是要放在它后面的数都已经放完了就可以放它了,它就是合法的了嘛,就是出度=0的时候就是合法的辣
另外,显然在拓扑的时候要把所有出边指向它的点的出边数量--嘛,那为了方便枚举点,就直接在建边的时候建反边就好
所以就反向建边拓扑排序倒叙输出就欧克辣!
听说这个是拓扑排序常见套路呢,,,?只是不知道我的学习总结要咕到哪天辣,,,如果以后写拓扑排序学习笔记什么的时候想起来辣这个点就还是cue一下昂qwq
然后有一个结论记下$QwQ$:
如果有一个排列$p$,满足若干偏序关系$p_i\leq p_j$,最小化$p^{-1}$的字典序的话,就$i->j$连边,跑一个最小拓扑序
如果是要最小化$p$的字典序,就跑反向图的最大拓扑序,再反过来
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define ll long long
#define gc getchar()
#define rp(i,x,y) for(rg ll i=x;i<=y;++i)
#define my(i,x,y) for(rg ll i=x;i>=y;--i) const ll N=+;
ll out[N],head[N],n,m,edge_cnt,as[N],as_cnt;
struct ed{ll to,nxt;}edge[N];
priority_queue<ll>Q; il ll read()
{
rg char ch=gc;rg ll x=;rg bool y=;
while(ch!='-' && (ch<'' || ch>''))ch=gc;
if(ch=='-')ch=gc,y=;
while(''<=ch && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void ad(ll x,ll y){edge[++edge_cnt]=(ed){y,head[x]};head[x]=edge_cnt;++out[y];}
il void topsort()
{
rp(i,,n)if(!out[i])Q.push(i);
while(!Q.empty())
{
ll nw=Q.top();Q.pop();as[++as_cnt]=nw;
for(rg ll i=head[nw];i;i=edge[i].nxt)if(!--out[edge[i].to])Q.push(edge[i].to);
}
if(as_cnt<n)return void(printf("Impossible!\n"));
rp(i,,as_cnt)printf("%lld ",as[n-i+]);printf("\n");
} int main()
{
freopen("cyzz.in","r",stdin);freopen("cyzz.out","w",stdout);
ll T=read();
while(T--)
{
edge_cnt=;as_cnt=;memset(head,,sizeof(head));memset(out,,sizeof(out));
n=read();m=read();rp(i,,m){ll x=read(),y=read();ad(y,x);}
topsort();
}
return ;
}
然后代码在这儿,记得清零什么的昂