首页 > 代码库 > Uva 10305 给任务排序
Uva 10305 给任务排序
题目链接:https://uva.onlinejudge.org/external/103/10305.pdf
紫书P167
拓扑排序。
dfs——从一个点出发,dfs 与之相连的所有点,把本身放入到拓扑排序的首部。
#include <bits/stdc++.h>using namespace std;const int Maxn = 1000;int G[Maxn][Maxn];int topo[Maxn];int c[Maxn];int n,m,t;bool dfs(int u) { c[u] = -1; for(int v=0;v<n;v++) if(G[u][v]) { if(c[v]<0) return false; else if(!c[v]&&!dfs(v)) return false; } c[u] = 1; topo[--t] = u; return true;}bool toposort() { t = n; memset(c,0,sizeof(c)); for(int u=0;u<n;u++) if(!c[u]) { if(!dfs(u)) return false; } return true;}int main(){ while(scanf("%d%d",&n,&m)==2&&n) { memset(G,0,sizeof(G)); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); u--; v--; G[u][v] = 1; } if(toposort()) { for(int i=0;i<n-1;i++) { printf("%d ",topo[i]+1); } printf("%d\n",topo[n-1]+1); } else printf("No\n"); } return 0;}
找入度为 0 的点,在这里开始删边。
#include <bits/stdc++.h>using namespace std;const int Maxn = 1100;int G[Maxn][Maxn];int degree[Maxn];int ans[Maxn];int main(){ int n,m; while(scanf("%d%d",&n,&m),n) { memset(degree,0,sizeof(degree)); memset(G,0,sizeof(G)); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); u--; v--; G[u][v] = 1; degree[v] ++; } int pos = 0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(degree[j]==0) { ans[pos++] = j; degree[j] = -1; for(int k=0;k<n;k++) { if(G[j][k]==1) degree[k]--; } } } } if(pos==n) { for(int i=0;i<n-1;i++) printf("%d ",ans[i]+1); printf("%d\n",ans[n-1]+1); } else puts("No"); } return 0;}
Uva 10305 给任务排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。