UVa 10305 Ordering Tasks:拓扑排序模板

UVa 10305 Ordering Tasks:拓扑排序模板2014-07-07 synapse7 10305 - Ordering Tasks

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1246模板题。注意倒着输出。

模板：

01./*0.022s*/02.03.#include<bits/stdc++.h>04.using namespace std;05.const int maxn = 101;06.07.list<int> li[maxn];08.bool vis[maxn];09.int ans[maxn], cnt;10.11.void dfs（int i）12.{13.vis[i] = true;14.if （li[i].size（））15.for （list<int>::iterator iter = li[i].begin（）; iter ！= li[i].end（）; ++iter）16.if （！vis[*iter]） dfs（*iter）;17.ans[cnt++] = i;18.}19.20.int main（）21.{22.int n, m, i, a, b;23.while （scanf（"%d%d", &n, &m）, n）24.{25.if （m == 0）26.{27.for （i = 1; i <= n; ++i）28.printf（"%d%c", i, （i == n ？ " " : 10））;29.continue;30.}31.for （i = 0; i < maxn; ++i） li[i].clear（）;32.memset（vis, 0, sizeof（vis））;33.cnt = 0;34.while （m--）35.{36.scanf（"%d%d", &a, &b）;37.li[a].push_back（b）;38.}39.for （i = 1; i <= n; ++i）40.if （！vis[i]） dfs（i）;41.for （i = n - 1; i; --i）42.printf（"%d ", ans[i]）;43.printf（"%d
", ans[0]）;44.}45.return 0;46.}