题解 | #[HNOI2015]菜肴制作#

#include<bits/stdc++.h>

using namespace std;
const int N=1e5+10;
int head[N],inc[N],ans[N];
int T,n,m,num,a1,a2;
struct ty{
    int y,next;
}edge[N];
void addedge(int x,int y)
{
    edge[++num].y=y;
    edge[num].next=head[x];
    head[x]=num;
}
int tuopu()
{
    priority_queue<int> q;
    int num=0;
    int i;
    for(i=1;i<=n;i++)
    {
        if(inc[i] == 0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int x = ans[++num] = q.top();
        q.pop();
        for(i = head[x] ; i != -1 ; i=edge[i].next)
        {
            int y=edge[i].y;
            inc[y]--;
            if(inc[y] == 0){
                q.push(y);
            }
        }
    }
    if(num < n)
    {
        return 0;
    }
    else{
        return 1;
    }
}

int main()
{
    cin >> T;
    int i;
    while(T--)
    {
        cin >> n >> m;
        num=0;
        memset(edge, 0, sizeof(edge));
        memset(head, -1, sizeof(head));
        memset(inc, 0, sizeof(inc));
        for(i=1;i<=m;i++)
        {
            cin >> a1 >> a2;
            addedge(a2,a1);
            inc[a1]++;
        }
        if(tuopu() == 0)
        {
            cout << "Impossible!";
        }
        else
        {
            for(i=n;i>=1;i--)
            {
                cout << ans[i] << " ";
            }
        }
        cout << endl;
        
    }
}