<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
JH和他的好朋友YZ两名程序员回访母校合工大，准备在这住一段日子，都说“玩在安大，吃在工大”，JH又是一名典型吃货，于是决定在工大食堂好好吃一段日子，但是，面对美食诱惑：黄焖鸡、风暴干锅、麻辣香锅、奥尔良烤翅…由于时间有限，JH不知道哪顿饭吃哪个菜好。 
于是YZ为了帮助他解决这个问题，也顺便考考他，给他出了一个问题：“黄焖鸡必须在干锅花菜前面吃，干锅牛肉必须在干锅鱿鱼前面吃….你按这个要求下，就知道吃的顺序啦”。JH抓抓头，分分钟写了个程序搞定，现在，让你来写写看？输出一组JH符合条件下吃的食物的序列。 
假设JH每顿只吃一种食物，且每顿吃的都不同，食物编号1到N。
</blockquote>

<h2 id="input">Input</h2>
<blockquote>
先输入一个整数T，表示T（T&lt;50）组数据。 
每组数据第一行输出一个整数，N,M,分别表示有N种食物，总共有M个约束条件，接下来M行每行输入两个正整数a,b(n&gt;=a&gt;0,n&gt;=b&gt;0)，表示食物a必须在食物b之前吃。
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
各组数据输出答案占一行，输出一组符合条件的序列（要求输出字典序最大的那一组），如果答案不存在，输出“-1”。
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
1 
4 3 
1 2 
2 3 
4 3
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
4 1 2 3
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
字典序的拓扑排序
普通的拓扑排序没有要求输出字典序最大的解，因此我们可以修改下来做
阅读以下内容，请确保已看过 <a href="/post/Algorithm/TopoSort.html">&gt;拓扑排序&lt;</a>
原本的拓扑排序，对于每一个源头，会尽可能将其遍历完再去遍历其他的源。
因此，当存在类似
<blockquote>
5 -&gt; 3 -&gt; 1 
2 -&gt; 4
</blockquote>
的关系时，会先把5当作源头，遍历完再去遍历以2为源的链
<blockquote>
5 -&gt; 3 -&gt; 1 -&gt; 2 -&gt; 4
</blockquote>
而非我们想要的答案
<blockquote>
5 -&gt; 3 -&gt; 2 -&gt; 4 -&gt; 1
</blockquote>
我们可以用类似于Dijkstra的形式，维护一个优先队列
当一个点被访问后(记录到结果里后)，所有以它为前置元素的元素(删除该点后，所有的源)都可以被访问了。
因此，每次取出优先队列中最大的元素进行拓扑排序，即可获得我们想要的答案。
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;set&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
using namespace std;

const int maxn = 1000;


bool G[maxn][maxn];

bool vis[maxn];

int n;

bool HasLoop() {
 //判断是否存在环
 for(int i = 1;i &lt;= n;i++)
 if(!vis[i])
 return false;
 return true;
}

bool IsStart(int k) {
 //判断是否入度为0
 for(int i = 1;i &lt;= n;i++)
 if(G[i][k])
 return false;
 return true;
}


bool TopoSort(int _n,int *ans) {
 //拓扑排序
 /*
 参数:
 邻接矩阵G[][]
 顶点数目n
 用于保存拓扑排序结果的数组 ans[]
 */
 //输出结果下标初始化
 int pos = 0;

 //已访问数组初始化
 memset(vis,false,sizeof(vis));

 //可被选择的数
 priority_queue&lt;int&gt; Q;

 //判断i是否为源
 for(int i = 1;i &lt;= n;i++) {
 if(IsStart(i))
 Q.push(i);
 }

 while(!Q.empty()) {
 int k = Q.top();
 Q.pop();

 if(vis[k])
 continue;
 else
 vis[k] = true;

 //记录到结果中
 ans[pos++] = k;

 for(int i = 1;i &lt;= n;i++) {
 if(G[k][i]) {
 //路径k~i存在
 //删除路径
 G[k][i] = false;
 //如果成为入度为0的点
 if(IsStart(i))
 Q.push(i);
 }
 }
 }

 //判断是否有环
 return HasLoop();
}



void Do() {
 memset(G,0,sizeof(G));
 int m;
 scanf(&#34;%d%d&#34;,&amp;n,&amp;m);
 for(int i = 0;i &lt; m;i++) {
 int a,b;
 scanf(&#34;%d%d&#34;,&amp;a,&amp;b);
 G[a][b] = 1;
 }

 int ans[maxn];
 if(TopoSort(n,ans)) {
 for(int i = 0;i &lt; n;i++) {
 if(i)
 printf(&#34; &#34;);
 printf(&#34;%d&#34;,ans[i]);
 }
 } else {
 printf(&#34;-1&#34;);
 }
 printf(&#34;\n&#34;);

}

int main() {
 int T;
 scanf(&#34;%d&#34;,&amp;T);
 while(T--)
 Do();
 return 0;
}
</pre>

HFUT 1359.吃在工大(安徽省2016“京胜杯”程序设计大赛 F)