首页 > 代码库 > UVa 10305 (拓扑排序) Ordering Tasks
UVa 10305 (拓扑排序) Ordering Tasks
题意：
经典的拓扑排序。有n个任务，然后某些任务必须安排在某些任务前面完成，输出一种满足要求的序列。
分析：
拓扑排序用离散里面的话来说就是将偏序关系拓展为全序关系。我们将“小于”这种关系看做一条有向边，如果得到的图是有向无环图DAG(Directed Acyclic Graph)，则是存在拓扑排序的，如果存在有向环，则不存在拓扑排序。
注意输入数据里面m可能等于0的情况，就因为这个WA了两次。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 105; 8 int G[maxn][maxn], c[maxn]; 9 int topo[maxn], t;10 int n, m;11 12 bool dfs(int u)13 {14 c[u] = -1;15 for(int v = 1; v <= n; ++v) if(G[u][v])16 {17 if(c[v] < 0) return false; //´æÔÚ»·18 else if(!c[v] && !dfs(v)) return false;19 }20 c[u] = 1; topo[--t] = u;21 return true;22 } 23 24 bool toposort()25 {26 t = n;27 memset(c, 0, sizeof(c));28 for(int u = 1; u <= n; ++u) if(!c[u])29 if(!dfs(u)) return false;30 return true;31 }32 33 int main(void)34 {35 #ifdef LOCAL36 freopen("10305in.txt", "r", stdin);37 #endif38 39 while(scanf("%d%d", &n, &m) == 2 && n)40 {41 memset(G, 0, sizeof(G));42 int a, b;43 for(int i = 0; i < m; ++i)44 {45 scanf("%d%d", &a, &b);46 G[a][b] = 1;47 }48 toposort();49 for(int i = 0; i < n-1; ++i)50 printf("%d ", topo[i]);51 printf("%d\n", topo[n-1]);52 }53 54 return 0;55 }
UVa 10305 (拓扑排序) Ordering Tasks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。