拓扑排序

定义：在一个有向图中，对所有的结点进行排序，要求没有一个结点指向它前面的结点

前提：有向无环图（DAG）

关键点：有向图、且不能形成环

算法描述：deg[100005]用来统计点i的度数（入度）

把所有入度为0的点插入到队列里

while(队列不空)
	取出队首点P
	访问P的所有相邻点Q，把它们的入度减一（就相当于把点P删了）
	如果Q入度被删成0了，点Q入列

我们边做循环，边统计结点们出队的顺序，这个出队顺序就是一个拓扑序，如果最后拓扑序不等于结点数，则不存在拓扑序

例题（HihoCoder - 1174 ）

问题描述

我们都知道大学的课程是可以自己选择的，每一个学期可以自由选择打算学习的课程。唯一限制我们选课是一些课程之间的顺序关系：有的难度很大的课程可能会有一些前置课程的要求。比如课程A是课程B的前置课程，则要求先学习完A课程，才可以选择B课程。大学的教务收集了所有课程的顺序关系，但由于系统故障，可能有一些信息出现了错误。现在小Ho把信息都告诉你，请你帮小Ho判断一下这些信息是否有误。错误的信息主要是指出现了"课程A是课程B的前置课程，同时课程B也是课程A的前置课程"这样的情况。当然"课程A是课程B的前置课程，课程B是课程C的前置课程，课程C是课程A的前置课程"这类也是错误的。

输入

第1行：1个整数T，表示数据的组数T(1 <= T <= 5)
接下来T组数据按照以下格式：
第1行：2个整数，N,M。N表示课程总数量，课程编号为1…N。M表示顺序关系的数量。1 <= N <= 100,000. 1 <= M <= 500,000
第2…M+1行：每行2个整数，A,B。表示课程A是课程B的前置课程。

输出

第1…T行：每行1个字符串，若该组信息无误，输出"Correct"，若该组信息有误，输出"Wrong"。

Sample Input

2
2 2
1 2
2 1
3 2
1 2
1 3

Sample Output

Wrong
Correct

关键点就在于判断这个图能否形成环，也就是判断这个图能否形成拓扑序

Code：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int t, n, m;
queue<int> qu;
vector<int> vv[100005];
int deg[100005];
bool vis[100005];
bool toposport() {
	int num = 0;//已经排序好的点的个数
	while (!qu.empty()) {
		int now = qu.front();
		qu.pop();
		num++;
		for (auto to : vv[now]) {
			if (vis[to]) {//经过我的测试，这里也可以没有
				continue;
			}
			else {
				deg[to]--;
				if (!deg[to]) {
					vis[to] = 1;//标记它是个入度为0的点
					qu.push(to);
				}
			}

		}
	}
	if (num == n) {
		return 1;
	}
	else {
		return 0;
	}
}
int main() {
	cin >> t;
	while (t--) {
		memset(deg, 0, sizeof(deg));
		memset(vis, 0, sizeof(vis));
		for (int i = 1; i <= 100000; i++) {
			vv[i].clear();
		}
		while (!qu.empty()) {
			qu.pop();
		}
		cin >> n >> m;
		for (int i = 1; i <= m; i++) {
			int a, b;
			cin >> a >> b;
			vv[a].push_back(b);
			deg[b] ++;//a指向b，那么b的入度自然要加一
		}
		for (int i = 1; i <= n; i++) {
			if (!deg[i]) {//如果入度为0，加入队列
				vis[i] = 1;
				qu.push(i);
			}
		}
		if (toposport()) {
			cout << "Correct" << endl;
		}
		else {
			cout << "Wrong" << endl;
		}
	}
}

例题2：HDU-2094
有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定，A一定能打败C。
如果A打败了B，B又打败了C，而且，C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。
Input
输入含有一些选手群，每群选手都以一个整数n(n<1000)开头，后跟n对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示，前者战胜后者。如果n为0，则表示输入结束。
Output
对于每个选手群，若你判断出产生了冠军，则在一行中输出“Yes”，否则在一行中输出“No”。
Sample Input
3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0
Sample Output
Yes
No
这题以前用set能过，后来学习了拓扑排序，发现这个题满足拓扑排序的特征，故重写一遍

在这里插入代码片#include<iostream>
#include<map>
#include<queue>
#include<cstring>
using namespace std;
vector<int> vv[1005];
bool book[1005];
int dis[1005];
int n;
map<string,int> mp;
queue<int> qu;
bool toposort(){
	int cnt=0;
	while(!qu.empty()){
		int now=qu.front();
		qu.pop();
		cnt++;
		if(book[now]){
			continue;
		}
		for(auto i:vv[now]){
			dis[i]--;
			if(dis[i]==0){
				book[i]=1;
				qu.push(i);
				
			}
		}
	}
	if(cnt==1){
		return 1;
	}else{
		return 0;
	}
	
}
int main(){
	while(scanf("%d",&n)!=EOF){
		memset(book,0,sizeof(book));
		memset(dis,0,sizeof(dis));
		if(n==0){
			break;
		} 
		for(int i=1;i<=n;i++){
			vv[i].clear();
		}
		mp.clear();
		int id=1;
		for(int i=1;i<=n;i++){
			string name1,name2;
			cin>>name1>>name2;
			if(!mp.count(name1)){
				mp[name1]=id++;
			}
			if(!mp.count(name2)){
				mp[name2]=id++;
			}
			vv[mp[name1]].push_back(mp[name2]);
			//cout<<mp[name1]<<"--->"<<mp[name2]<<endl;
			dis[mp[name2]]++;
		}
		for(int i=1;i<=mp.size();i++){
			if(!dis[i]){
				book[i]=1;
				qu.push(i);
			}
		}
		if(toposort()){
			cout<<"Yes"<<endl;
		}else{
			cout<<"No"<<endl;
		}
	}
	
}