题目大意:
给出n个任务和m条边,从第二行输入开始,每行x y表示x任务要在y之前完成,针对任务优先级这样一个关系要你输出一个top序列(任意,因为序列不唯一)。
思路:
我看刘汝佳写的dfs感觉挺麻烦的,其实top排序很简单:建图,找n个点的序列,每个找点遍历每个点,找到入度为0的点,把它的出度去掉并且标记已访问,然后一直这样找下去,直到找到n个点为止。
代码:
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=110;
int g[maxn][maxn];
int has[maxn];
int top[maxn];
int n,m;
bool check(int x){
for(int i=1;i<=n;i++){
if(g[i][x])return false;
}
return true;
}
void clear(int x){
for(int i=1;i<=n;i++){
g[x][i]=0;
}
}
int main(){
while(scanf("%d%d",&n,&m)&&(n||m)){
memset(g,0,sizeof(g));
memset(has,0,sizeof(has));
memset(top,0,sizeof(top));
int x,y;
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
g[x][y]=1;
}
int cnt=0;
while(cnt<n){
for(int i=1;i<=n;i++){
if(has[i])continue;
if(check(i)){
top[cnt]=i;
has[i]=1;
cnt++;
clear(i);
break;
}
}
}
cout<<top[0];
for(int i=1;i<n;i++){
cout<<" "<<top[i];
}
cout<<endl;
}
}