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

//反向建边，在正常的拓扑排序里面我们只能按照起始的点去寻找最大或最小的字符序列，
//但是在题目当中要求尽量先吃到质量高的菜肴，那么这就关系到终点了。
//所以我们可以采用反向建边的方式，去求一个字符序列最大的，这样就实现了尽量先吃到质量高的菜肴。
#include <bits/stdc++.h>
using namespace std;
#define int long long
//使用链式前向星存储。
const int maxn = 100000+10;
struct sy{
    int to;
    int next;
} edge[maxn];
map<pair<int,int>, int> mp;
struct comp{
    bool operator () (const int &x, const int &y) const {
        return x<y;
    }
};
int in[maxn];
int head[maxn];
priority_queue<int, vector<int>, comp> pq;
int cnt = 0;

void add_edge(int x, int y)
{
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    head[x] = cnt;
}

void solve()
{
    while (pq.size()) pq.pop();
    memset(in, 0, sizeof(in));
    memset(head, -1, sizeof(head));
    mp.clear();
    for (int i=0;i<maxn;i++) edge[i].next=0,edge[i].to=0;
    cnt = 0;
    int n, m;
    int x, y;
    vector<int> ans;
    cin>>n>>m;    
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y;
        if (mp[{x,y}]==0)
        {
//             cout<<"x="<<x<<" y="<<y<<endl;
            mp[{x, y}] = 1;
            add_edge(y, x);
            in[x]++;
        }
    }
    //遍历一遍节点，选出能够选出来的第一批人进入优先队列里面
    for (int i=1;i<=n;i++)
    {
        if (in[i]==0) pq.push(i);
    }
    while (pq.size())
    {
        int number = pq.top();
//         cout<<"number="<<number<<endl;
        pq.pop();
        ans.push_back(number);
        for (int i=head[number];i!=-1;i = edge[i].next)
        {
//             cout<<"i="<<i<<endl;
            in[edge[i].to]--;
            if (in[edge[i].to]==0)
                pq.push(edge[i].to);
        }
    }
    if (ans.size()!=n) cout<<"Impossible!";
    else 
        for (int i=n-1;i>=0;i--)
        {
            cout<<ans[i]<<' ';
        }
    cout<<"\n";
}

signed main()
{
    int D;
    cin>>D;
    while (D--)
    {
        solve();
    }
    return 0;
}