Link

Description

有$n$道菜，编号越小的越美味（最美味的是$1$号菜品）。现在给出一些形如$(i,j)$的限制，表示$i$号菜品必须在$j$号菜品之前制作。要求出一个最优的菜肴的制作顺序，使得Karry5307能尽量先吃到美味的菜肴。无解输出Impossible!

Sol

如果你是贪心地求字典序小的，Karry5307不一定能吃到尽量先地吃到最美味的菜品。

比如说共4 道菜肴，两条限制$(3,1)$、$(4,1)$，那么制作顺序是 $3,4,1,2$。但是你贪心就会变成$2,3,4,1$但是如果反过来处理，建一个反图，求一个反向字典序最大的拓扑序。那么就会有大的数尽量靠前的情况出现，于是交小的数尽量靠后，于是反过来就是小的数尽量靠前了。

Code

果然代码环节还是我最喜欢的

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

const int SIZE = 1e5 + 5;

int q, n, m, num;
int head[SIZE], deg[SIZE];

struct node {
    int to, nxt;
} edge[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void addEdge(int u, int v)
{
    edge[++ num].to = v, edge[num].nxt = head[u];
    head[u] = num;
}

inline void top()
{
    std::priority_queue < int > q;
    std::vector < int > ans;
    for (int i = 1; i <= n; ++ i) {
        if (!deg[i]) q.push(i);
    }
    while (!q.empty()) {
        int u = q.top(), v;
        ans.push_back(u);
        q.pop();
        for (int i = head[u]; i; i = edge[i].nxt) {
            v = edge[i].to;
            -- deg[v];
            if (!deg[v]) q.push(v);
        }
    }
    if ((int) ans.size() != n) puts("Impossible!");
    else {
        for (auto i = ans.end() - 1; i != ans.begin() - 1; -- i) printf("%d ", *i);
        putchar('\n');
    }
}

int main()
{
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    q = read();
    while (q --) {
        n = read(), m = read();
        for (int i = 1, u, v; i <= m; ++ i) {
            u = read(), v = read();
            addEdge(v, u); ++ deg[u];
        }
        top();
        num = 0;
        memset(head, 0, sizeof(head));
        memset(deg, 0, sizeof(deg));
    }
    return 0;
}