John有n个任务要做，每个任务在做之前要先做特定的一些任务。
输入第一行包含两个整数n和m，其中1<=n<=100。 n表示任务数，而m表示有m条任务之间的关系。 接下来有m行，每行包含两个整数i和j，表示任务i要在j之前做。
当读入两个0（i=0，j=0）时，输入结束。
输出包含q行，每行输出一条可行的安排方案。
题目的意思是要按顺序做任务，我们可以把所有二元组转化为一条单向边，也就是要保证所有边的u都在v的前面。这个问题其实就是图论中的拓扑排序。如果在拓扑排序的过程中出现了环，那么就说明不可能存在合理的拓扑排序。我们只需要进行一次dfs就可以完成拓扑排序的过程。在dfs中我们把最深的点放在拓扑序的最深处，因为最深处的点一定是最大的点。对于没有出现在图里的节点。我们随意插入即可。
#include <cstdio> #include <cstring> int n, m, c[110], topo[110], t, a1[110][110]; bool dfs(int u) { c[u]=-1; for(int v=0;v<n;v++) { if(a1[u][v]) if(c[v]<0)return false; else if(!c[v]&&!dfs(v))return false; } c[u]=1;tope(--t)=u; return ture } i void toposort() { t = n; for ( int u = 1; u <= n; ++u ) if ( !c[u] ) dfs(u); } int main() { while ( scanf("%d%d", &n, &m) != EOF && !( !m && !n) ) { memset( map, 0, sizeof(map) ); memset( c, 0, sizeof(c) ); while ( m-- ) { int a, b; scanf("%d%d", &a, &b); map[a][b] = 1; } toposort(); printf("%d", topo[0]); for ( int i = 1; i < n; ++i ) printf(" %d", topo[i]); printf("\n"); } }
原文：https://www.cnblogs.com/tscjj/p/13735095.html