题目描述
知名美食家小 A被邀请至ATM 大酒店，为其品评菜肴。 ATM 酒店为小 A 准备了 N 道菜肴，酒店按照为菜肴预估的质量从高到低给予1到N的顺序编号，预估质量最高的菜肴编号为1。
由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 M 条形如”i 号菜肴'必须'先于 j 号菜肴制作“的限制，我们将这样的限制简写为<i,j>。
现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A能尽量先吃到质量高的菜肴
思路
首先，让编号小的菜尽量向前是错误的，反例如：<2,3><4,1>，按编号小的尽量前得出的答案为 2,3,4,1，而正确答案为 4,1,2,3。
这个是错误的原因是不能保证最小的被先吃。考虑反过来，让编号大的菜靠后，就可以使前面的编号尽可能的小，所以在反图上跑拓扑，有环答案就是 Impossible
代码
/************************************************
*Author : lrj124
*Created Time : 2019.11.14.11:13
*Mail : [email protected]
*Problem : luogu3243
************************************************/
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
using pii = pair<int,int>;
const int maxn = 100000 + 10;
int d,n,m,ans[maxn],deg[maxn];
vector<int> edge[maxn];
inline void toposort() {
priority_queue<int> q;
for (int i = 1;i <= n;i++) if (!deg[i]) q.push(i);
for (int now;q.size();) {
now = q.top(); q.pop();
ans[++ans[0]] = now;
for (size_t i = 0;i < edge[now].size();i++) {
int to = edge[now][i];
if (!--deg[to]) q.push(to);
}
}
}
int main() {
freopen("luogu3243.in","r",stdin);
freopen("luogu3243.out","w",stdout);
for (scanf("%d",&d);d--;ans[0] = 0) {
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++) { deg[i] = 0; edge[i].clear(); }
for (int i = 1,u,v;i <= m;i++) {
scanf("%d%d",&u,&v); deg[u]++;
edge[v].push_back(u);
}
toposort();
if (ans[0] ^ n) puts("Impossible!");
else for (int i = ans[0];i;i--) printf("%d%c",ans[i],i ^ 1 ? ' ' : '\n');
}
return 0;
}