当前位置: 代码迷 >> 综合 >> 例题6-15 UVa10305 Ordering Tasks(拓扑排序)
  详细解决方案

例题6-15 UVa10305 Ordering Tasks(拓扑排序)

热度:4   发布时间:2024-01-16 13:55:31.0

题意:

看白书

要点:

1.拓扑排序:将一个图上的所有结点排序,使得每一条有向边(u,v)对应的u都排在v后面。注意只有有向无环图(DAG)才有拓扑排序

2.利用dfs先将最深的赋值给数组中最后一个位置,相同深度的就随便排了,因为只输出一种,所以答案跟题目中给的可以不一样

3.注意其中的c[n]数组,c[u]=0说明从来没有访问过(即从来没有调用过dfs(u),需要在toposort中使用),c[u]=-1说明正在访问(即递归调用dfs(u)正在栈帧中,尚未返回),c[u]=1说明已经访问过,而且还递归访问过它的所有子孙(即dfs(u)曾被调用过,并已返回,toposort不在访问u)。


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int c[150],topo[150];
bool g[150][150];
int m, n,t;bool dfs(int u)
{c[u] = -1;           //为-1说明在堆栈中,正在递归for (int v = 1; v <= n; v++){if (g[u][v]){if (c[v] == -1)  return false;		//出现有环就脱离else if (!c[v] && !dfs(v)) return false;//还是在判断是否有环}} c[u] = 1;			//为1说明已经完成递归,后面就不再参与toposorttopo[--t] = u;      //递归中是倒序的,所以先脱离的反而大return true;
}bool toposort()
{t = n;memset(c, 0, sizeof(c));for (int i = 1; i <= n; i++)if (!c[i]&&!dfs(i))return false;return true;
}
int main()
{while (~scanf("%d%d", &n, &m), m + n){memset(g, false, sizeof(g));int v, u,i;for (i = 0; i < m; i++){scanf("%d%d", &u, &v);g[u][v] = true;}if (toposort()){for (i = 0; i < n - 1; i++)printf("%d ", topo[i]);printf("%d\n", topo[i]);}}return 0;
}


  相关解决方案