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

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int din[N];
vector<int> ans;

template<class T>
inline void read(T& res)
{
    char ch; bool flag = false;
    while ((ch = getchar()) < '0' || ch > '9')
        if (ch == '-') flag = true;
    res = ch ^ 48;
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = (res << 1) + (res << 3) + (ch ^ 48);
    if (flag) res = ~res + 1;
}

void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}

bool topsort()
{
    priority_queue<int> q;
    ans.clear();
    for (int i = 1; i <= n; i ++)
        if (!din[i])
            q.push(i);
            
    while (!q.empty())
    {
        int t = q.top();
        q.pop();
        ans.push_back(t);
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (-- din[j] == 0) q.push(j);
        }
    }
    return ans.size() == n;
}

void getAC()
{
    read(n), read(m);
    memset(din, 0, sizeof din);
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 0; i < m; i ++)
    {
        int x, y; scanf("%d%d", &x, &y);
        add(y, x);
        din[x] ++;
    }
    
    if (!topsort()) puts("Impossible!");
    else
    {
        for (int i = ans.size() - 1; i >= 0; i --) printf("%d ", ans[i]);
        puts("");
    }
}

int main()
{
    int t; cin >> t;
    while (t --) getAC();
    
    return 0;
}