题目描述
John有n个任务要做，每个任务在做之前要先做特定的一些任务。
输入第一行包含两个整数n和m，其中1<=n<=100。 n表示任务数，而m表示有m条任务之间的关系。 接下来有m行，每行包含两个整数i和j，表示任务i要在j之前做。
当读入两个0（i=0，j=0）时，输入结束。
输出包含q行，每行输出一条可行的安排方案。
输入
5 4 1 2 2 3 1 3 1 5 0 0
输出
1 4 2 5 3
思路:拓扑序列的简单使用.这次使用的是紫书上的DFS方法来求解的.
参考代码
#include<iostream> #include<string.h> using namespace std; const int maxn = 110; int n,m,G[maxn][maxn],book[maxn],topo[maxn],t; bool dfs(int u){ book[u] = -1;//做标记 for(int v = 1;v <= n; v++) { if(G[u][v]){ if(book[v]<0){//如果之前访问过则说明有环. return false;//有环 }else if(!book[v]){//如果没有被访问过就进行dfs访问. dfs(v); } } } book[u] = 1;//标记已经访问过. topo[t--] = u;//存入序列 return true;//此节点及其子节点无环 } bool TopoSort(){ t = n; memset(book,0,sizeof(book)); for(int i = 1; i <= n;i++){ if(!book[i]){//如果没有被访问过 if(!dfs(i)){ return false;//如果有环 } } } return true; } int main() { int u,v; while(cin>>n>>m&&n){ //数据初始化 memset(G,0,sizeof(G)); //memset(book,0,sizeof(book)); memset(topo,0,sizeof(topo)); t = n; for(int i = 1;i <= m; i++){ cin>>u>>v; G[u][v] = 1; } if(TopoSort()){ for(int i = 1;i < n;i++){ cout<<topo[i]<<" "; } cout<<topo[n]<<endl; } else{ cout<<"No"<<endl; } } return 0; }
