定義：對一個有向無環(huán)圖G進行拓撲排序，是將G中所有頂點排成一個線性序列葛虐，使得圖中任意一對頂點u和v胎源，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前屿脐。通常涕蚤，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列的诵。簡單的說万栅，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序西疤。
hdu1285
問題描述：
有N個比賽隊（1<=N<=500）烦粒，編號依次為1，2代赁，3扰她，兽掰。。义黎。禾进。，N進行比賽廉涕，比賽結束后泻云，裁判委員會要將所有參賽隊伍從前往后依次排名，但現(xiàn)在裁判委員會不能直接獲得每個隊的比賽成績狐蜕，只知道每場比賽的結果宠纯，即P1贏P2，用P1层释，P2表示婆瓜，排名時P1在P2之前。現(xiàn)在請你編程序確定排名贡羔。
輸入：
輸入有若干組廉白，每組中的第一行為二個數(shù)N（1<=N<=500），M乖寒；其中N表示隊伍的個數(shù)猴蹂，M表示接著有M行的輸入數(shù)據(jù)。接下來的M行數(shù)據(jù)中楣嘁，每行也有兩個整數(shù)P1磅轻，P2表示即P1隊贏了P2隊。
輸出：
給出一個符合要求的排名逐虚。輸出時隊伍號之間有空格聋溜，最后一名后面沒有空格。
其他說明：符合條件的排名可能不是唯一的叭爱，此時要求輸出時編號小的隊伍在前撮躁；輸入數(shù)據(jù)保證是正確的，即輸入數(shù)據(jù)確保一定能有一個符合要求的排名涤伐。
Sample Input
4 3
1 2
2 3
4 3
Sample Output
1 2 4 3
思路：為了讓代碼簡單馒胆，p1贏了p2，用p1 -> p2表示凝果。
根據(jù)樣例可以得到下圖：
由圖可知沒有隊伍贏1和4，也就是說第一名要么是1要么是4睦尽，又由題意編號小的排在前面器净，所以可以得到第一名為1。對于都贏了3的2和4当凡，標號小的排在前面山害，所以第二名為2纠俭，接著是3和4。
可以發(fā)現(xiàn)是先從入度為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;
//當兩個隊伍不能確定名次時外邓，編號小的排在前面，所以需要用到優(yōu)先隊列
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的老師庞萍。
思路：很容易發(fā)現(xiàn)拧烦，存在矛盾的樣例的圖一定存在環(huán)。而拓撲排序是判斷是否有環(huán)的很好算法挂绰。即如果從隊列中取出的點不等于n屎篱，就一定存在環(huán)。
注：不能由隊列是否為空來判斷葵蒂，當n - 2, 1->2, 2->1時隊列也為空交播，當這是有環(huán)的。只有當每個點取出践付，才可以確定沒有環(huán)秦士。
/*有些題給的數(shù)據(jù)可能會重復，即給了重邊永高，也不會有影響隧土。
如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;
}
題意：老板發(fā)獎金瑟由，每個工人至少888元，而有些工人存在著要求冤寿，a和b歹苦，a要求他的獎金要比b高。給你n個工人疚沐，編號為1到n暂氯，m個要求，求老板總共最低需要給這些工人多少獎金亮蛔。不能滿足他們的要求就輸出-1痴施。
思路：不能滿足要求，即存在環(huán)究流。當滿足要求時辣吃，最小的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;
}
