题意:给出n个任务,任务不是完全独立的,有些任务必须依赖另外一些任务才能执行;m个任务关系。

输出:n个任务的可能执行顺序;

我的解决方法:这就是个赤裸裸的拓扑排序,直接dfs拓扑每一个任务点,然后再加入没有列入拓扑排序的任务点,集中输出就可以了。

 #include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 110
using namespace std; int mat[MAXN][MAXN],num[MAXN],vis[MAXN],cnt; void dfs(int x,int n){//递归搜索每个任务;
vis[x]=-;
for(int i=;i<=n;i++)if(mat[x][i]){
if(!vis[i])dfs(i,n);
}
vis[x]=;
num[--cnt]=x;
} void topo_sort(int n){//拓扑排序;
for(int i=;i<=n;i++)
if(!vis[i])dfs(i,n);
} int main(){
int n,m;
while(scanf("%d%d",&n,&m),n||m){
cnt=n;
memset(vis,,sizeof(vis));
memset(mat,,sizeof(mat));
int p,q;
for(int i=;i<m;i++){
scanf("%d%d",&p,&q);
if(p!=q)mat[p][q]=;//去掉环;
}
topo_sort(n);
for(int i=;i<=n;i++)//加入没有排序的任务;
if(!vis[i])vis[i]=,num[--cnt]=i;
int first=;
for(int i=;i<n;i++){
if(first){printf("%d",num[i]);first=;}
else printf(" %d",num[i]);
}
printf("\n");
}
return ;
}

最新文章

  1. HDU 2087  KMP模板题
  2. 【JavaWeb】MVC案例之新闻列表
  3. Objective-C数据类型之id,SEL,BOOL,nil,NULL和NSNull
  4. css3之过渡
  5. SDUT 2408:Pick apples
  6. cocos2d-x 用浏览器打开网页
  7. WebStrom9 体验nodejs
  8. jboss之mod_cluster集群
  9. wordpress换域名后无法登陆的解决方案
  10. Java反射的理解
  11. $and $not null 正则表达式
  12. Spring Security(三十四):10.4 Jackson Support
  13. UOJ#314. 【NOI2017】整数 其他
  14. Docker网络模式说明
  15. CF444(Div. 1简单题解)
  16. 003-Go初探Iris
  17. mac 安装配置java环境变量
  18. 微信公众号开发者模式自定义菜单 node
  19. 更改VS Code界面为简体中文
  20. linux中,如何设置每隔2个小时就执行一次某个脚本?

热门文章

  1. FZU 1686 神龙的难题 (重复覆盖)
  2. NPOI操作excel
  3. PostGIS ShapeFile 导入数据
  4. python中的告警处理
  5. openvpn安装
  6. Linux中find常见用法
  7. leveldb 学习笔记之VarInt
  8. hbuilder中如何使用egit上传项目
  9. Crystal Reports拉报表报错:Error detected by database DLL
  10. IIS配置excel 权限