一、拓扑排序

定义： 拓扑排序是将一个有向无环图的所有顶点排成一个线性队列，并且保证队中的所有点不会指向其前面的点，即所有边只能是某个点指向其队列后面的点。
排序原理： 首先存下所有点的入度（有几条边的终点是该点），若某点入度为0，将该点加入拓扑序，然后删除该点为起点的所有边（就是将所有该点为起点的边的终点的入度减一），然后重复此操作，直到所有顶点进入拓扑序即可。若有点未进入拓扑序，说明该图存在环。

二、代码实现

1、邻接表的拓扑排序

#include<iostream>
#include<vector>
#include<queue>using namespace std;
const int N = 110;int n,m;	//顶点数和边数
int e[N][N],d[N];	//e为邻接矩阵数组，d为顶点入度数组
vector<int> ans;	//ans为拓扑序数组即为最终答案
queue<int> q;	//队列q存入度为0的点void topsort()
{for(int i = 1;i <= n;i++)	//找出初始所有入度为0的点if(d[i] == 0)q.push(i);	//入队qwhile(!q.empty()){int t = q.front();	//记录队首顶点，处理以他为起点的边q.pop();ans.push_back(t);	//q的队首进入拓扑序for(int j = 1;j <= n;j++)	//遍历其他所有点{if(e[t][j] == 1)	//若存在以他为起点的边{d[j]--;		//删除此边，其终点的入度-1if(d[j] == 0)	//如果终点的入度为0，入队q.push(j);}}}
}int main()
{int a,b;cin >> n >> m;for(int i = 0;i < m;i++){cin >> a >> b;	//输入边e[a][b] = 1;	//存图d[b]++;		//终点的入度+1}topsort();	//拓扑排序for(int i = 0;i < ans.size();i++)cout << ans[i] << endl;return 0;
}

2、邻接表的拓扑排序

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>using namespace std;
const int N = 110;int n,m;	//顶点数和边数
int h[N],e[N],ne[N],idx;	//用数组模拟邻接表
int d[N];	//入度数组
vector<int> ans;	//拓扑序数组，即为答案void add(int a,int b)	//加边函数，存一条a到b的边
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void topsort()
{queue<int> q;for(int i = 1;i <= n;i++)	//找到初始时所有入度为0的点if(d[i] == 0)q.push(i);	//入队qwhile(!q.empty()){int t = q.front();	//记录队首元素q.pop();ans.push_back(t);	//入拓扑序for(int i = h[t]; ~i;i = ne[i])	//找到所有以该点为起点的边{int k = e[i];	//寻找以该点为起点的下一个点d[k]--;		//删去此边，即此点入度-1if(d[k] == 0)	//若入度为0，入队q.push(k);}}
}int main()
{int a,b;cin >> n >> m;memset(h,-1,sizeof h);for(int i = 0;i < m;i++){cin >> a >> b;	//输入边d[b]++;		//终点的入度+1add(a,b);	//存边}topsort();	//拓扑排序for(int i = 0;i < ans.size();i++)cout << ans[i] << endl;return 0;
}

三、经典例题

1、可达性统计
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。（1≤N,M≤30000）

计算a点可到达点的数量只需计算a点所能到达的所有点的可达点之和再加上自己（1）。所以先将所有点拓扑排序，然后从后往前计算每个点能到达的点的可达点数量之和，再+1即可。
由于点的数量太大达到30000，直接计算肯定会超时，所以这里用状态压缩将所有点压缩成二进制，每一位的0或1代表能否到达该点，这里直接使用stl的bitset比较方便

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<bitset>using namespace std;
const int N = 30010;int n,m;	//n点m边
int h[N],e[N],ne[N],idx;	//邻接表存图
int d[N];	//入度数组
vector<int> ans;	//拓扑序数组
bitset<N> f[N];		//二进制数组，f的每一个元素均为一个n位的二进制数void add(int a,int b)	//加边函数
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}void topsort()		//拓扑排序
{queue<int> q;for(int i = 1;i <= n;i++)if(d[i] == 0)q.push(i);while(!q.empty()){int t = q.front()ans.push_back(t);q.pop();for(int i = h[t]; ~i;i = ne[i]){int j = e[i];d[j]--;if(d[j] == 0)q.push(j);}}
}void calc()	//计算可达点
{for(int i = ans.size()-1;i >= 0;i--)	//从后往前计算{int k = ans[i];f[k][k] = 1;	//表示f[k]的第k位为1，k到k先记为1for(int j = h[k];~j;j = ne[j])	//列举所有k能到达的点{f[k] |= f[e[j]];	//k点的可达点数量就是k点所有可达点的可达点数量和，将k点和其所有可达点按位或，即该点的某位为1则都为1}}
}int main()
{int a,b;cin >> n >> m;for(int i = 0;i < m;i++){cin >> a >> b;d[b]++;add(a,b);}topsort();calc();for(int i = 1;i <= n;i++)cout << f[i].count() << endl;	//f[i].count()表示f[i]的按位1的个数return 0;
}