题目描述
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;
}