拓扑排序

看这个部分的原因是什么呢？啊，我忘记了，可能是数据老师上课的时候讲过恰巧听见了？(~~完全没有听过课~~)，也可能是看了一眼发现其实并不难，然后就总结一下吧。

当然我肯定不是自己靠意念学会的，主要就是看了CSDN的一篇文章，很不错，受益匪浅！在开始我自己的”复述”之前，就先把他的链接放下吧！拓扑排序入门（真的很简单）_安得广厦千万间的博客-CSDN博客_拓扑排序。实际上这位大神确实讲的很清楚了，我写的原因是为了温习自己所学，以后看自己的文字也更亲切一点吧！

什么是拓扑排序？

首先拓扑排序必须是在一个有向无环图(DAG)中，把入度为0的节点输出，直到所有的节点都输出，所输出的序列就是拓扑排序的序列。

拓扑排序示意图.jpg

如上图所示，a的入度为0输出a，c的入度为0输出c ……最终得到的序列就是acbfde

当然，由于在同一时间可能有多个节点的入度为0，那么拓扑排序所得的序列就不是唯一的，而让他变成唯一的可能就是用到拓扑排序的题的精髓所在(如：字典序，倒序，数小优先等等……)

如果看了以上的内容你还是懵懵懂懂，那么，举一个生活上的例子：小明是体育委员，他想给同学们按照身高来排队，他每次只能对比两个同学的身高，经过两个两个人的比较，最终就可以得到排好的队伍(由部分的对比来完成整体的对比)

拓扑排序的朴素写法

CODE：

int a[N];//入度值
bool pos[N][N]; //边
int main(){	
    int n,m,x,y,tmp;
    cin>>n>>m;//n个人，m对关系
    for(int i=1;i<=m;i++) {
        cin>>x>>y;
        if(pos[x][y]==false) {
            pos[x][y] = true; //从x可以到达y 
            a[y]++; //y入度+1 
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {//遍历入度为0的节点
            if(a[j]==0) {
                cout<<j<<" "; //输出序列，也可以用数组/vector保存
                a[j]--;
                tmp = j;
                break;
            }
        }
        for(int j=1;j<=n;j++) 
            if(pos[tmp][j])
                a[j]--;
	return 0;
}

解释：

很容易就能想到朴素写法，就是不断的遍历节点，直到所有节点都输出了(注意如果有重复输入的关系，可能需要加一点东西)。

朴素的写法的复杂度是O(n^2)。很容易看出来，确实好写，大多数情况感觉用不到。。

优化版的写法

CODE：

queue<int> q;
vector<int> edge[n];
for(int i=1;i<=n;i++)  //n  节点的总数
    if(in[i]==0) 
        q.push(i);  //将入度为0的点入队列
vector<int> res;   //ans 为拓扑序列
while(!q.empty())
{
    int tmp=q.front(); q.pop(); // 选一个入度为0的点，出队列
    res.push_back(tmp);
    for(int i=0;i<edge[tmp].size();i++)
    {
        int x=edge[p][i];
        in[x]--;
        if(in[x]==0)
            q.push(x);  
    }
}
if(res.size()==n)   
{
    for(int i=0;i<res.size();i++)
        printf( "%d ",res[i] );
    printf("\n");
}
else printf("No Answer!\n");   //  ans 中的长度与n不相等，就说明无拓扑序列

解释：

这样的复杂度是O(n+m)点和边的和，太好了吧！！这样就是把每次用n来遍历一个节点换成用队列来遍历，这样的话减完以后变成0的节点直接放在队伍后面就可以了，那么实际上就会跑节点数量和边的数量的和！

例题1 - ly的排队问题

CODE:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7; 
string s;
int come[N];//入度
priority_queue<int,vector<int>,greater<int> > q; //从小到大字典序
vector<int> edge[100],res;//存边，存结果
set<int> k;//是否出现
void solve(){
	for(int i=0;i<26;i++)//一共26个字母
		if(k.count(i) && come[i]==0)
			q.push(i);
	while(!q.empty()) {
		int tmp = q.top();q.pop();
		res.push_back(tmp);
		for(int i=0;i<edge[tmp].size();i++) {
			int x = edge[tmp][i];
			come[x]--;
			if(come[x]==0 && k.count(x))
				q.push(x);
		}
	}
	if(res.size()==k.size()) {
		for(int i=0;i<res.size();i++)
			putchar(res[i]+'A');
		cout<<endl;
	}
	else
		cout<<"No Answer!"<<endl;
} 
int main(){	
	while(cin>>s) {
		int x = s[0] - 'A';
		int y = s[2] - 'A';
		k.insert(x);k.insert(y);
		if(s[1]=='>') {
			edge[x].push_back(y);
			come[y]++;
		}
		else {
			edge[y].push_back(x);
			come[x]++;
		}
	}//上面就是建图的过程
	solve();
	return 0;
}

例题2 - 逃生

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7; 
priority_queue<int> q;//队列
vector<int>link[N],res;//边，答案
int come[N];
int n,m,x,y;
void solve() {
	
	for(int i=1;i<=n;i++)
		if(come[i]==0)
			q.push(i);
	while(!q.empty()) {
		int tmp = q.top();q.pop();
		res.push_back(tmp);
		for(int i=0;i<link[tmp].size();i++) {
			int v = link[tmp][i];
			come[v]--;
			if(come[v]==0)
				q.push(v);
		}
	}
	for(int i=res.size()-1;i>0;i--)//倒序输出
		cout<<res[i]<<" ";
	cout<<res[0]<<endl;
}
void init() {//重置数组
	for(int i=1;i<=n;i++) {
		link[i].clear();
		come[i] = 0;
	}
	while(!q.empty())	q.pop();
	res.clear();
}
int main(){	
	int _;cin>>_;
	while(_--) {	
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<=m;i++) {
			scanf("%d%d",&x,&y);
			link[y].push_back(x);
			come[x]++;
		}// 反向建图
		solve();
	} 
	return 0;
}