【题解】LuoGu3243：[HNOI2015]菜肴制作

原题传送门
题意：
给出一张有向无环图，求一个遍历序，要求其每个点在 被遍历之前要保证它的入度点已经全部被遍历，在此基础上 满足
编号最小的尽量靠前，在此基础上编号次小的尽量靠 前……编号最大的尽量靠后。
求一个方案。图的点数、边数 均不超过10^5。

solution:
拓扑+堆
但是不能顺着做，发现题意的要求并不是裸的字典序最小
但是如果反向建边，求字典序最大，最后反向输出可以达到最优并且满足题目要求

多组数据需要注意初始化

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
priority_queue <int> q;
int n, m, num, in[maxn], head[maxn], print[maxn];
struct Edge{
	int to, next;
}edge[maxn << 1];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge) { y, head[x] }; head[x] = num; }

int main(){
	int M = read();
	while (M--){
		n = read(), m = read();
		memset(head, 0, sizeof(head));
		num = 0;
		memset(in, 0, sizeof(in));
		for (int i = 1; i <= m; ++i){
			int x = read(), y = read();
			++in[x]; addedge(y, x);
		}
		for (int i = 1; i <= n; ++i)
			if (!in[i]) q.push(i);
		int cnt = 0;
		while (!q.empty()){
			int u = q.top(); q.pop();
			print[++cnt] = u;
			for (int i = head[u]; i; i = edge[i].next){
				int v = edge[i].to;
				if (!(--in[v])) q.push(v);
			}
		}
		if (cnt < n) printf("Impossible!\n"); else{
			for (int i = cnt; i; --i) printf("%d ", print[i]); puts("");
		}
	}
	return 0;
}