John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is
only possible if other tasks have already been executed.
Input
The input will consist of several instances of the problem. Each instance begins with a line containing
two integers, 1 ≤ n ≤ 100 and m. n is the number of tasks (numbered from 1 to n) and m is the
number of direct precedence relations between tasks. After this, there will be m lines with two integers
i and j, representing the fact that task i must be executed before task j.
An instance with n = m = 0 will finish the input.
Output
For each instance, print a line with n integers representing the tasks in a possible order of execution.
Sample Input
5 4
1 2
2 3
1 3
1 5
0 0
Sample Output
1 4 2 5 3
约翰有n个任务要做， 不幸的是，这些任务并不是独立的，执行某个任务之前要先执行完其他相关联的任务
题解：拓扑排序模版题；
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define PI(x) printf("%d",x)
#define P_ printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
const int MAXN=110;
int que[MAXN];
int mp[MAXN][MAXN];
int n;
int vis[MAXN];
int ans[MAXN];
void topu(){
int k=0,a;
mem(vis,0);
while(k<n){
int temp=INF;
for(int i=1;i<=n;i++){
if(!vis[i]&&que[i]==0){
ans[k++]=i;temp=i;
break;
}
}
if(temp==INF)break;
vis[temp]=1;
for(int i=1;i<=n;i++)if(mp[i][temp]){
que[i]--; }
}
for(int i=0;i<k;i++){
if(i)P_;
PI(ans[i]);
}
puts("");
}
int main(){
int m,a,b;
while(scanf("%d%d",&n,&m),n|m){
mem(que,0);
mem(mp,0);
while(m--){
SI(a);SI(b);
que[b]++;
mp[b][a]=1;
}
topu();
}
return 0;
}
dfs也可以写拓扑排序：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define PI(x) printf("%d",x)
#define P_ printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
const int MAXN=110;
int mp[MAXN][MAXN];
int vis[MAXN],ans[MAXN];
int n;
int k;
bool dfs(int u){
vis[u]=-1;
for(int i=1;i<=n;i++){
if(mp[u][i]){
if(vis[i]==-1)return false;//表示结点v正在访问中，(即调用dfs(u)还在栈中，尚未返回)
if(!vis[i])dfs(i);
}
}
ans[--k]=u;
vis[u]=1;
return true;
}
bool topu(){
mem(vis,0);
k=n;
for(int i=1;i<=n;i++){
if(!vis[i])if(!dfs(i))
return false;
}
for(int i=0;i<n;i++){
if(i)P_;
PI(ans[i]);
}
puts("");
return true;
}
int main(){
int m,a,b;
while(scanf("%d%d",&n,&m),n|m){
mem(mp,0);
while(m--){
SI(a);SI(b);
mp[a][b]=1;
}
topu();
}
return 0;
}