问题分析

我们需要在满足所有先后顺序约束的前提下，找到一个拓扑排序，使得编号小（质量高）的菜肴尽可能靠后。这与传统的字典序最小拓扑排序正好相反。

关键观察

1. 问题本质

这是一个拓扑排序问题，但目标不是通常的字典序最小，而是：

在满足约束的前提下，让 $1$ 号尽量靠后

在 $1$ 号尽量靠后的前提下，让 $2$ 号尽量靠后

依此类推...

这等价于求反向图的字典序最大拓扑排序。

2. 算法选择

传统拓扑排序：使用队列，得到的是编号小的先出现

本题要求：编号大的先出现，编号小的尽量靠后

因此应该：

1.建反向图（$y \to x$ 而不是 $x \to y$）

2.使用大根堆而不是队列来进行拓扑排序

算法思路

1. 图构建

for (int i = 1; i <= m; ++i) {
    scanf("%lld%lld", &x, &y);
    gra[y].push_back(x);  // 反向建边
    ++rd[x];              // x的入度增加
}

将约束 $\langle x, y \rangle$（$x$ 必须在 $y$ 之前）转化为边 $y \to x$。

2. 拓扑排序过程

// 初始化：所有入度为0的节点入堆
for (int i = 1; i <= n; ++i) {
    if (!rd[i]) {
        tp.push(i);  // 大根堆，编号大的优先
    }
}

// 拓扑排序主循环
while (!tp.empty()) {
    int x = tp.top();  // 取当前编号最大的可用节点
    tp.pop();
    stk[++stk[0]] = x;  // 存入结果栈
    
    // 处理后继节点
    for (auto i : gra[x]) {
        --rd[i];
        if (!rd[i]) {
            tp.push(i);  // 新的可用节点入堆
        }
    }
}

3. 结果输出

if (stk[0] != n) {
    printf("Impossible!");  // 存在环，无解
} else {
    while (stk[0]) {
        printf("%lld ", stk[stk[0]--]);  // 逆序输出得到正确顺序
    }
}

正确性证明

为什么反向建边 + 大根堆有效？

设原约束为 $\langle x, y \rangle$（$x$ 在 $y$ 前）：

正向图：$x \to y$，拓扑排序时 $x$ 先于 $y$

反向图：$y \to x$，拓扑排序时 $y$ 先于 $x$

在反向图中使用大根堆：

每次选择编号最大的可用节点

这保证了编号小的节点尽量晚出现

最终结果栈逆序后就是满足题目要求的顺序

复杂度分析

时间复杂度：$O((n + m) \log n)$

每个节点入堆一次：$O(n \log n)$

每条边处理一次：$O(m)$

空间复杂度：$O(n + m)$

样例验证

样例1

输入：

5 4
5 4
5 3  
4 2
3 2

处理过程：

1.反向建边：$4\to5$, $3\to5$, $2\to4$, $2\to3$

2.拓扑排序得到栈：$[2, 4, 3, 5, 1]$

3.逆序输出：$1, 5, 3, 4, 2$

样例2

输入：

3 3
1 2
2 3
3 1

存在环 $1\to2\to3\to1$，输出"Impossible!"

样例3

输入：

5 2
5 2
4 3

拓扑排序得到栈：$[3, 4, 2, 5, 1]$，逆序输出：$1, 5, 2, 4, 3$

关键技巧

1.反向建图：将"前驱"关系转化为"后继"关系

2.大根堆：优先选择编号大的节点，让编号小的尽量靠后

3.栈存储+逆序输出：得到最终的拓扑顺序

总结

本题通过巧妙的图变换：

将"质量高的尽量靠前"转化为"编号小的尽量靠后"

通过反向建图 + 大根堆拓扑排序解决

最终逆序输出得到正确答案

算法高效处理了 $n, m \leq 10^5$ 的大规模数据，是拓扑排序应用的经典例题。