拓扑排序（Topological Sorting）

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

只有有向无环图才有拓扑排序，另外的图没有拓扑排序一说。

ps：对于拓扑排序来说，判断是否是有向无环图是关键。

#include
using namespace std;
int n,m;
//建边，每个顶点能到哪些点：G[0]={1,2,3}代表 0 能到  1，2，3这些顶点 
vectorG[20];
//用来标记顶点的状态：0-->未访问;1-->已访问;-1-->正在访问; 
int vis[20];
vectorans; 
// 判断是否可以进行拓扑排序 
void init(){
	for(int i=1;i<=n;i++){
		g[i].clear;
		vis[i]=0;
	}
} 
bool dfs(int x){
	//标记x点正在被访问；
	vis[x]=-1;
	//通过x点，判断下一个点是否可到，进行遍历	
	for(int i=0;i>n>>m){
		init();
		for(int i=0;i>a>>b;
			G[a].push_back(b);
		}
		if(!topo_sort()){
			cout<<"-1"<=0;i--){
			cout<

         广搜拓扑写法居多（从入度和出度的角度考虑）。

#include
using namespace std;
int n,m;
vectorG[20];
int in[20]; 
void init(){
	for(int i=1;i<=n;i++){
		G[i].clear();
		in[i]=0;
	}
} 
int main(){
	while(cin>>n>>m){
		init();
		for(int i=0;i>a>>b;
			G[a].push_back(b);
			//b入度增加 
			in[b]++;
		}
		queueq;
		int sum=n;
		//将所有入度为零的点加入到队列中
		for(int i=1;i<=n;i++){
			if(in[i]==0){
				q.push(i);
				sum--;
			}
		} 
		vectorans;
		//广搜跑拓扑排序
		while(!q.empty()){
			int len=q.size();
			for(int i=0;i