[HNOI2015]菜肴制作

题意

见https://www.luogu.org/problemnew/show/P3243

题解

在反向图上拓扑排序，用小根堆维护

调试记录

数组开小了100倍

#include 
#include 
#include 
#include 
using namespace std;
priority_queue ,less > q;
int from[1000000],to[1000000],head[1000000],nxt[1000000],cnt=0;
int n,m;
int ans[1000000];
void add(int x,int y){
    cnt++;
    to[cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
    from[y]++;
}
int main(){
    int T,x,y;
    cin>>T;
while (T--){
    cnt=0;
    memset(head,0,sizeof(head));
    memset(nxt,0,sizeof(nxt));
    memset(from,0,sizeof(from));
    while (!q.empty()) q.pop();
    int sum=0,flag=0;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>x>>y;
        if (x==y) flag=1;
        add(y,x);
    }
    if (flag) {
        cout<<"Impossible!"<<endl;
        continue;
    }
    for (int i=1;i<=n;i++)
        if (!from[i])
            q.push(i);
    while (!q.empty()){
        int t=q.top();
        sum++;
        ans[sum]=t;
        q.pop();
        for (int i=head[t];i;i=nxt[i]){
            from[to[i]]--;
            if (from[to[i]]==0)
                q.push(to[i]);
        }
    }
    if (sum!=n) cout<<"Impossible!"<<endl;
    else{
        for (int i=1;i<=n;i++)
            cout<<ans[n-i+1]<<' ';
        cout<<endl;
    }
}
    return 0;
}