#反向建边 #拓扑排序

题意

• 有n个菜，m个条件约束条件(a,b)，表a必须在b之前
• 除了约束条件外，要保证序号小的的尽可能先做
• 在满足所有限制的前提下，1 号菜肴”尽量“优先制作；
• 在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作；
• 以此类推。
• 例：共4 道菜肴，两条限制<3,1>、<4,1>，那么制作顺序是 3,4,1,2。

思路

• 正向描述这个拓扑序不好描述，因为每做一个菜都可能影响当前的“最优先做的菜”
• 考虑反向描述
• 先做序号最小的->最后做序号最大的
• 通过反向建边，变为在拓扑序中寻找字典序最大的

代码

#include<bits/stdc++.h>
using namespace std;

struct E{
    int t,nxt;
}edge[101010];
int head[101010];
int inc[101010];
int cnt;


int n,m;

void insert(int a,int b){
    edge[++cnt].t=b;
    edge[cnt].nxt=head[a];
    head[a]=cnt;
}

priority_queue<int> q;
int ans[101010];
int cnt1;
bool tuopu(){
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++){
        if(inc[i]==0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int x=q.top();
        q.pop();
        ans[++cnt1]=x;
        for(int i=head[x];i!=-1;i=edge[i].nxt){
            inc[edge[i].t]--;
            if(inc[edge[i].t]==0){
                q.push(edge[i].t);
            }
        }
    }
    if(cnt1<n) return false;
    else return true;
}

int main(){
    int d;
    cin >> d;
    while(d--){
        cnt=cnt1=0;
        memset(head,-1,sizeof(head));
        memset(inc,0,sizeof(inc));
        cin >> n >> m;
        for(int i=1;i<=m;i++){
            int a,b;
            cin >> a >> b;
            insert(b,a);
            inc[a]++;
        }
        if(!tuopu()) cout << "Impossible!" << endl;
        else{
            for(int i=n;i>=1;i--){
                cout << ans[i] << ' ';
            }
            cout << endl;
        }
    }

}