首页 > 代码库 > UVa 10305 (拓扑排序) Ordering Tasks

UVa 10305 (拓扑排序) Ordering Tasks

2024-07-24 05:11:20   225人阅读

题意：

经典的拓扑排序。有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


联系
我们