問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3687思路:
這題理解起來就很困難，等理解透了也還是不會
參考:
http://hi.baidu.com/archersfate/blog/item/30e66f76734a0c12b051b9ab.html總結:
逆向的拓撲排序，等同于對轉置圖進行正向的拓撲排序（其實就是入度與出度的區別）
DFS實現拓撲排序適合于求出所有可能的解
BFS實現拓撲排序適合于求出滿足特定要求的解
代碼:
1 /* cpp: priority_queue */
2 #include<iostream>
3 #include<queue>
4 #include<vector>
5 #include<functional>
6 #include<cstdio>
7 #include<cstring>
8 using namespace std;
9
10 #define MAX_N 201
11 int n, m;
12 int adj[MAX_N][MAX_N];
13 int out_degree[MAX_N], topo[MAX_N], ans[MAX_N];
14
15 void
16 init()
17 {
18 int i, pre, suc;
19 memset(adj, 0, sizeof(adj));
20 memset(out_degree, 0, sizeof(out_degree));
21 scanf("%d %d", &n, &m);
22 for(i=0; i<m; i++) {
23 scanf("%d %d", &pre, &suc);
24 if(!adj[pre][suc]) { /* avoid duplicates */
25 adj[pre][suc] = 1;
26 ++out_degree[pre];
27 }
28 }
29 }
30
31 void
32 reverse_topo_sort()
33 {
34 int i, tmp, count = 0;
35 priority_queue<int, vector<int>, less<int> > Q;
36 for(i=1; i<=n; i++)
37 if(out_degree[i] == 0)
38 Q.push(i);
39 while(!Q.empty()) { /* BFS */
40 tmp = Q.top();
41 Q.pop();
42 topo[++count] = tmp;
43 for(i=1; i<=n; i++)
44 if(adj[i][tmp]) {
45 --out_degree[i];
46 if(!out_degree[i])
47 Q.push(i);
48 }
49 }
50 if(count != n) { /* not DAG */
51 printf("-1\n");
52 return;
53 }
54 for(i=1; i<=n; i++)
55 ans[topo[n-i+1]] = i;
56 for(i=1; i<=n; i++)
57 printf("%d ", ans[i]);
58 printf("\n");
59 }
60
61 int
62 main(int argc, char **argv)
63 {
64 int tests;
65 scanf("%d", &tests);
66 while(tests--) {
67 init();
68 reverse_topo_sort();
69 }
70 }
轉載:
PKU 3687 在基本的拓撲排序的基礎上又增加了一個要求：編號最小的節點要盡量排在前面；在滿足上一個條件的基礎上，編號第二小的節點要盡量排在前面；在滿足前兩個條件的基礎上，編號第三小的節點要盡量排在前面……依此類推。（注意，這和字典序是兩回事，不可以混淆。）
如圖 1 所示，滿足要求的拓撲序應該是：6 4 1 3 9 2 5 7 8 0。
圖 1 一個拓撲排序的例子
一般來說，在一個有向無環圖中，用 BFS 進行拓撲排序是比較常見的做法
做法，如算法 1 所示。但是它不一定能得到本題要求的拓撲序。
1. 把所有入度為 0 的節點放進隊列 Q
2. WHILE： Q 不是空隊列
3. 從 Q 中取出隊列首元素 a，把 a 添加到答案的尾部。
4. FOR：所有從 a 出發的邊 a → b
5. 把 b 的入度減 1。如果 b 的入度變為 0，則把 b 放進隊列 Q。 |
算法 1 用 BFS 進行拓撲排序
為了解決本問題，下面讓我來探究一下拓撲序的一些性質。以圖 1 為例，節點 0 毫無疑問排在最后。除了節點 0 以外，有三條互相平行的路徑：6 → 4 → 1、 3→ 9 → 2 和 5 → 7 → 8。一條路徑上的各個節點的先后關系都是不能改變的，比如路徑 6 → 4 → 1 上的三個節點在拓撲序中，一定是 6 在最前，1 在最后。但是，互相平行的各條路徑，在總的拓撲序中任意交錯都是合法的。比如，以下都是圖 1 的合法拓撲序：
6 4 1 3 9 2 5 7 8 0、 3 6 9 4 5 1 7 8 2 0、 5 6 4 7 3 8 1 9 2 0、 3 5 6 4 1 7 9 2 8 0、 6 5 7 8 4 3 9 2 1 0。
怎么才能找出題目要求的拓撲序呢？在這里，我想用字典序最先的拓撲序來引出這個算法。算法 2 可以求出字典序最先的拓撲序。
1. 把所有入度為 0 的節點放進優先隊列 PQ
2. WHILE： PQ 不是空隊列
3. 從 PQ 中取出編號最小的元素 a，把 a 添加到答案的尾部。
4. FOR：所有從 a 出發的邊 a → b
5. 把 b 的入度減 1。如果 b 的入度變為 0，則把 b 放進優先隊列 PQ。 |
算法 2 求出字典序最先的拓撲序
可見，算法 2 和算法 1 基本一樣，只是把隊列改成了優先隊列。用它求出的圖 1 的字典序最先的拓撲序為：3 5 6 4 1 7 8 9 2 0。但是這顯然不是本題要求的答案，因為節點 1 的位置還不夠靠前。
算法 2 可以算是一個貪心算法，每一步都找編號最小的節點。但是對于圖 1 中的三條路徑，頭的編號比較小的，不一定要先出隊列。正確的步驟應該如下：
- 節點 0 的位置是鐵定在最后的，不用考慮。只考慮剩下的三條路徑。
- 先找編號最小的，節點 1。把它和它所在的路徑中位于它前面的節點全部拿出來。目前的答案是 6 4 1，這樣， 節點 1 就盡量靠前了。
- 再找剩下的節點中編號最小的，節點 2。把它和它所在的路徑中位于它前面的節點全部拿出來。目前的答案是 6 4 1 3 9 2 ，這樣，節點 2 就盡量靠前了。
- 只剩下一條路徑了，只能依次把其中的節點拿出來。最后答案就是 6 4 1 3 9 2 5 7 8 0。
顯然，算法 2 的貪心策略對于這個問題是不可行的。不能著眼于每條路徑的頭，而是要找編號最小的節點在哪條路徑上，優先把這條路徑拿出來。但問題在于，在 BFS 的過程中，我們只能看到每條路徑的頭，看不到后面的節點，這該怎么辦呢？
讓我們換個角度想一想，節點 3 和 6，應該是 6 先出隊列，因為節點 1 在 6 的后面。這和節點 3 和 6 的編號大小沒有任何關系。但是，再看另外兩條路徑的尾部，節點 2 和 8，可以肯定地說，2 一定先出隊列，因為它們后面都沒有別的節點了，這個時候完全以這兩個節點本身的編號大小決定順序。歸納起來就是說，對于若干條平行的路徑，小的頭部不一定排在前面，但是大的尾部一定排在后面。于是，就有了算法 3。
1. 把所有出度為 0 的節點放進優先隊列 PQ
2. WHILE： PQ 不是空隊列
3. 從 PQ 中取出編號最大的元素 a，把 a 添加到答案的頭部。
4. FOR：所有指向 a 的邊 b → a
5. 把 b 的出度減 1。如果 b 的出度變為 0，則把 b 放進優先隊列 PQ。 |
算法 3 求出本題目要求的拓撲序
我覺得這道題目確實挺奧妙的，我搞了很久才想通算法 3 為什么是正確的，特地在此寫一下。