首页 > 代码库 > UVa 10305 给任务排序
UVa 10305 给任务排序
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1246
题意就是最普通的拓扑排序,输出可能的排序结果。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int maxn = 1000; 5 6 int n, m, cuv[maxn][maxn], c[maxn], topo[maxn], t; 7 8 bool dfs(int u) 9 { 10 c[u] = -1; 11 for (int v = 1; v<=n; v++) if (cuv[u][v]) 12 { 13 if (c[v]<0) return false; //存在有向环。 14 else if (!c[v] && !dfs(v)) return false; 15 } 16 c[u] = 1; topo[--t] = u; 17 return true; 18 } 19 20 bool toposort() 21 { 22 t = n; 23 memset(c, 0, sizeof(c)); 24 for (int u = 1; u <= n; u++) if (!c[u]) 25 if (!dfs(u)) return false; 26 return true; 27 } 28 29 int main() 30 { 31 while (cin >> n >> m && n) 32 { 33 memset(cuv, 0, sizeof(cuv)); 34 for (int i = 1; i <= m; i++) 35 { 36 int u, v; 37 cin >> u >> v; 38 cuv[u][v] = 1; 39 } 40 if (toposort()) 41 { 42 for (int i = 0; i < n - 1; i++) 43 cout << topo[i] << " "; 44 cout << topo[n - 1] << endl; 45 } 46 else 47 printf("No\n"); 48 } 49 return 0; 50 }
2016-12-11 10:42:03
UVa 10305 给任务排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。