预备知识
- 开始学图论了，紫书上拓扑排序的入门题，在洛谷找到了它拿来练手。
- 一篇关于拓扑排序的很透彻的博客，如果你还不了解拓扑排序，可以看完了再回来刷这条题目。
题意翻译
John有n个任务要做，每个任务在做之前要先做特定的一些任务。
输入第一行包含两个整数n和m，其中1<=n<=100。 n表示任务数，而m表示有m条任务之间的关系。 接下来有m行，每行包含两个整数i和j，表示任务i要在j之前做。
当读入两个0（i=0，j=0）时，输入结束。
输入输出样例
输入样例#1：
5 4
1 2
2 3
1 3
1 5
0 0
输出样例#1：
1 4 2 5 3
输出包含q行，每行输出一条可行的安排方案。
分析
- 拓扑排序有两个经典算法kahn算法和基于dfs的算法，这里我们采取后者。
- 先说说坑点，这题有多组输入，不要被样例的一组给骗了。
- 题目没说无解的情况怎么输出，大概就是无解输出-1。
- 首先如果存在环路，那么拓扑排序就无法进行，那么如何判断环路呢，我们可以用一个vis数组记录每个点的访问状况，值为-1时表示正在访问，如果递归时重复的遇到这个状态就说明存在环路，为0时表示还没有访问，为1时表示已经访问过了。
- 用一个topo数组记录答案，记录答案时要从后往前，想一想为什么(提示：递归)
代码
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 110;
/* top数组的指针，用于从后往前记录答案
* G 邻接矩阵存图
*/
int n, m, top;
int G[maxn][maxn], vis[maxn];
bool dfs(int u){
vis[u] = -1;
for (int j = 1; j <= n; ++j){
if (G[u][j]){
if (vis[j] < 0)
return false;
else if (!vis[j] && !dfs(j))
return false;
}
}
vis[u] = 1;
topo[top--] = u;
return true;
}
bool topo_sort(){
top = n;
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; ++i){
if (!vis[i] && !dfs(i))
return false;
}
return true;
}
int main(int argc, char const *argv[]){
while (scanf("%d%d", &n, &m) == 2 && n){
int u, v;
for (int i = 1; i <= m; ++i){
scanf("%d%d", &u, &v);
G[u][v] = 1;
}
if (!topo_sort()){
printf("%d ", -1);
}else {
for (int i = 1; i <= n; ++i)
printf("%d ", topo[i]);
}
printf("\n");
}
return 0;
}
