在合法范围内最后一个数字越大越优,然后变成子问题,所以建反图字典序最大的拓扑排序,经典套路

#include<bits/stdc++.h>
using namespace std;
const int maxn=100009;
int n,m;
struct node{
    int v,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add(int u,int v){
    e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int in[maxn],st[maxn],top;
priority_queue<int>q;
int main(){int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(e,0,sizeof(e));
        memset(head,0,sizeof(head));
        memset(in,0,sizeof(in));
        top=0;cnt=0;
        for(int i=1,u,v;i<=m;i++){
            scanf("%d%d",&u,&v);
            add(v,u);in[u]++;
        }
        for(int i=1;i<=n;i++)if(!in[i])q.push(i);
        while(!q.empty()){
            int x=q.top();q.pop();st[++top]=x;
            for(int i=head[x];i;i=e[i].nxt){
                int y=e[i].v;
                if(!--in[y])q.push(y);
            }
        }
        if(top!=n){
            printf("Impossible!\n");
            continue;
        }
        for(;top>=1;top--)printf("%d ",st[top]);puts("");
    }

}
01-13 03:41