「HNOI2015」菜肴制作

传送门
Luogu

解题思路

很容易想到建图突然后拓扑排序跑最小字典序。
但这个显然不对，具体原因自己yy一下就行了。
我们建一张反图，然后跑字典序最大方案，倒序输出就好了。
至于正确性，显然想一想为什么（留坑）

细节注意事项

• 咕咕咕

参考代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
	s = 0; int f = 0; char c = getchar();
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
	s = f ? -s : s;
}

const int _ = 100010;

int tot, head[_], nxt[_], ver[_];
inline void Add_edge(int u, int v)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }

int n, m, dgr[_], ans[_];
priority_queue < int > Q;

inline void solve() {
	memset(dgr, 0, sizeof dgr);
	while (!Q.empty()) Q.pop();
	tot = 0;
	memset(head, 0, sizeof head);
	read(n), read(m);
	int flag = 0;
	for (rg int u, v; m--; )
		read(u), read(v), Add_edge(v, u), ++dgr[u], flag |= u == v;
	if (flag) { puts("Impossible!"); return; }
	for (rg int i = 1; i <= n; ++i)
		if (!dgr[i]) Q.push(i);
	int cnt = 0;
	while (!Q.empty()) {
		int u = Q.top(); Q.pop(), ans[++cnt] = u;
		for (rg int i = head[u]; i; i = nxt[i])
			if (!--dgr[ver[i]]) Q.push(ver[i]);
	}
	if (cnt < n) { puts("Impossible!"); return; }
	for (rg int i = cnt; i; --i)
		printf("%d%c", ans[i], " 
"[i == 1]);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
#endif
	int T; read(T);
	while (T--) solve();
	return 0;
}

完结撒花 (qwq)