Contents
Problem
題目網址
中文網址
找出做事情的順序,事情有一定的相依關係,如:在做 B 之前,必須先完成 A。
p.s. 答案可能不是唯一解。
Solution
關於 拓撲排序
直接邊做拓撲排序邊印出即可。
Code
UVa 10305UVa 10305 - Ordering Tasks
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
|
#include<deque> #define N 101 using namespace std;
deque<int> DQ[N]; void (int n); int main() { int n, i, j; while (scanf("%d", &n) && n) { for (i = 1; i <= n; i++) DQ[i].clear();
int m, a, b; scanf("%d", &m); for (j = 0; j < m; j++) { scanf("%d%d", &a, &b); DQ[a].push_back(b); }
topo(n); }
return 0; } void (int n) { int ref[N] = {}, i; for (i = 1; i <= n; i++) for (int j : DQ[i]) ref[j]++;
deque<int> Q; for (i = 1; i <= n; i++) { if (!ref[i]) Q.push_back(i); }
bool first = true; while (!Q.empty()) { if (!first) putchar(' '); else first = false;
int s = Q.front(); Q.pop_front();
ref[s] = -1; printf("%d", s); for (int j : DQ[s]) { ref[j]--; if (!ref[j]) Q.push_back(j); }
}
putchar('n'); }
|
近期评论