Ordering Tasks
题目链接:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=18723
题目大意:
有一些任务需要完成,其中有些任务必须比另一些任务先完成。让你按照完成时间的先后顺序对任务进行排序。
解题思路:
拓扑排序:
搜索该图的顶点,把所有只有出度没有入度的点输出,然后把与这些点相连的点的入度减一。重复该过程即可
同样,也可用dfs函数来完成拓扑排序:
int c[105], g[105][105], n, t; int topo[105]; bool dfs(int u) { c[u] = -1; for (int v = 1; 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; mem(c, 0); for (int i = 1; i <= n; i++) if (!c[i]) if (!dfs(i)) return false; return true; }
用c数组,c[u] = 0 表示从来没有调用过dfs(u), c[u] = 1 表示已经访问过,并且还递归访问过它所有子孙,c[u] = -1, 表示正在访问。
实现代码:
#include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<set> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 1000 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; using namespace std; int c[105], g[105][105], n, t; int topo[105]; bool dfs(int u) { c[u] = -1; for (int v = 1; 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; mem(c, 0); for (int i = 1; i <= n; i++) if (!c[i]) if (!dfs(i)) return false; return true; } int main () { int m; while(cin>>n>>m) { mem(g, 0); if (n + m == 0) break; int u, v; while(m--) { scanf("%d%d", &u, &v); g[u][v] = 1; } toposort(); printf("%d", topo[0]); for (int i = 1; i < n; i++) printf(" %d", topo[i]); puts(""); } return 0; }