定义：对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
hdu1285
问题描述：
有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。
输入：
输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。
输出：
给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。
其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。
Sample Input
4 3
1 2
2 3
4 3
Sample Output
1 2 4 3
思路：为了让代码简单，p1赢了p2，用p1 -> p2表示。
根据样例可以得到下图：
由图可知没有队伍赢1和4，也就是说第一名要么是1要么是4，又由题意编号小的排在前面，所以可以得到第一名为1。对于都赢了3的2和4，标号小的排在前面，所以第二名为2，接着是3和4。
可以发现是先从入度为0的点开始找，它指向的下一个点，也就是排名在它后面的点。当去掉入度为0的点时，它指向的点的入度也相应减1。即下一次，就可能是它的下一个点。
因此可以得到如下代码：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <algorithm>
#include <iterator>
using namespace std;
#define PI 3.14159265
#define e 2.71828182
typedef long long ll;
typedef pair<int, int> P;
const int MAX_N = 1 << 17;
const int INF = 0x3f3f3f3f;
int ind[MAX_N]; //每个点入度
vector<int> g[MAX_N]; //存图
priority_queue<int, vector<int>, greater<int> > que;
//当两个队伍不能确定名次时，编号小的排在前面，所以需要用到优先队列
void solve(int n) {
for (int i = 1; i <= n; ++i) {
if (ind[i] == 0) que.push(i);
}
bool flag = false;
while (que.size()) {
int k = que.top();
que.pop();
if (!flag) {
printf("%d", k);
flag = true;
}
else printf(" %d", k);
for (int i = 0; i < g[k].size(); ++i) {
--ind[g[k][i]];
if (ind[g[k][i]] == 0) que.push(g[k][i]);
}
}
while (!que.empty()) que.pop();
printf("\n");
}
int main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0; i <= n; ++i) {
ind[i] = 0;
g[i].clear();
}
for (int i = 0; i < m; ++i) {
int p1, p2;
scanf("%d%d", &p1, &p2);
++ind[p2];
g[p1].push_back(p2);
}
solve(n);
}
return 0;
}
hdu3342
题意：给出n人的编号为 0到n-1,再给出m个关系。A和B，A是B的老师。问这些关系是否存在矛盾，即不能存在A是B的老师，B是C的老师，而C是A的老师。
思路：很容易发现，存在矛盾的样例的图一定存在环。而拓扑排序是判断是否有环的很好算法。即如果从队列中取出的点不等于n，就一定存在环。
注：不能由队列是否为空来判断，当n - 2, 1->2, 2->1时队列也为空，当这是有环的。只有当每个点取出，才可以确定没有环。
/*有些题给的数据可能会重复，即给了重边，也不会有影响。
如1->2存了两次，取出1后，遍历1指向的点，第一次到2，将2的入度减1， 因为入度不为0，所以不会push。
第二次入度减一，入度为0，才会push。也就是说遍历完1指向的点，只会push进队列一个2。
*/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <algorithm>
#include <iterator>
using namespace std;
#define PI 3.14159265
#define e 2.71828182
typedef long long ll;
typedef pair<int, int> P;
const int MAX_N = 1 << 17;
const int INF = 0x3f3f3f3f;
int ind[MAX_N];
vector<int> g[MAX_N];
queue<int> que;
bool solve(int n) {
for (int i = 0; i < n; ++i) {
if (ind[i] == 0) que.push(i);
}
int cnt = 0;
while (que.size()) {
int k = que.front();
que.pop();
++cnt;
for (int i = 0; i < g[k].size(); ++i) {
--ind[g[k][i]];
if (ind[g[k][i]] == 0) que.push(g[k][i]);
}
}
while (que.size()) que.pop();
return cnt == n;
}
int main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
int n, m;
while (scanf("%d%d", &n, &m) != EOF && n > 0) {
for (int i = 0; i <= n; ++i) {
ind[i] = 0;
g[i].clear();
}
for (int i = 0; i < m; ++i) {
int p1, p2;
scanf("%d%d", &p1, &p2);
++ind[p2];
g[p1].push_back(p2);
}
bool ans = solve(n);
printf("%s\n", ans ? "YES" : "NO");
}
return 0;
}
题意：老板发奖金，每个工人至少888元，而有些工人存在着要求，a和b，a要求他的奖金要比b高。给你n个工人，编号为1到n，m个要求，求老板总共最低需要给这些工人多少奖金。不能满足他们的要求就输出-1。
思路：不能满足要求，即存在环。当满足要求时，最小的b得888，向上依次加1。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <algorithm>
#include <iterator>
using namespace std;
#define PI 3.14159265
#define e 2.71828182
typedef long long ll;
typedef pair<int, int> P;
const int MAX_N = 1 << 17;
const int INF = 0x3f3f3f3f;
int ind[MAX_N];
vector<int> g[MAX_N];
queue<P> que;
int solve(int n) {
for (int i = 1; i <= n; ++i) {
if (ind[i] == 0) que.push((P){i, 0});
}
int ans = 0;
int cnt = 0;
while (que.size()) {
P k = que.front();
que.pop();
++cnt;
ans += 888 + k.second;
for (int i = 0; i < g[k.first].size(); ++i) {
--ind[g[k.first][i]];
if (ind[g[k.first][i]] == 0){
que.push((P){g[k.first][i], k.second + 1});
//下一个点只需要比指向它的点大一即可
}
}
}
if (cnt != n) ans = -1;
while (que.size()) que.pop();
return ans;
}
int main() {
//ios::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 0; i <= n; ++i) {
ind[i] = 0;
g[i].clear();
}
for (int i = 0; i < m; ++i) {
int p1, p2;
scanf("%d%d", &p1, &p2);
++ind[p1];//需要先让p2出来，因为p1比p2高，最终可得最底层p2为888
g[p2].push_back(p1);
}
int ans = solve(n);
printf("%d\n", ans);
}
return 0;
}
