题解
这道题目首先可以想到拓扑排序，但是肯定不是字典序最小的排列。
比如说，有\(4\)种菜，限制为\(2 \to 4, 3 \to 1\)，那么如果求字典序最小的排列会算出\((2, 3, 1, 4)\)，但是答案显然是\((3, 1, 2, 4)\)。
于是，正难则反，发现如果最后一个数字在合法的范围内尽可能的大，那么就会更优。
我们就可以求字典序反序最大的排列。
于是建反图，跑拓扑排序即可，这里的拓扑排序要用到堆。
代码
#include#include #include #include #include #define RG register#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);#define clear(x, y) memset(x, y, sizeof(x))inline int read(){ int data = 0, w = 1; char ch = getchar(); while(ch != '-' && (!isdigit(ch))) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar(); return data * w;}const int maxn(3e5 + 10);std::priority_queue heap;struct edge { int next, to; } e[maxn];int head[maxn], e_num, n, m, deg[maxn], T, cnt, ans[maxn];inline void add_edge(int from, int to){ e[++e_num] = (edge) {head[from], to}; head[from] = e_num; ++deg[to];}int main(){ T = read(); while(T--) { clear(head, 0); e_num = 0; clear(deg, 0); n = read(); m = read(); int f = 0; cnt = 0; for(RG int i = 1, x, y; i <= m; i++) { x = read(), y = read(), add_edge(y, x); if(x == y) f = 1; } if(f) { puts("Impossible!"); continue; } for(RG int i = 1; i <= n; i++) if(!deg[i]) heap.push(i); while(!heap.empty()) { int x = heap.top(); heap.pop(); ans[++cnt] = x; for(RG int i = head[x]; i; i = e[i].next) { int to = e[i].to; if(!(--deg[to])) heap.push(to); } } if(cnt < n) puts("Impossible!"); else { for(RG int i = n; i; i--) printf("%d ", ans[i]); puts(""); } } return 0;}