问题:
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 为什么是正确的，特地在此写一下。