拓扑序列（拓扑排序）

摘要

本文主要介绍拓扑序列，和求解拓扑序列的方法。

什么是拓扑序列

拓扑序列是对于有向图而言的，有向图的拓扑序是其顶点的线性排序，使得对于从顶点$u$u 到顶点$v$v的每个有向边$uv$uv， $u$u 在序列中都在$v$v之前。

例如对于下图：

对于上图， 存在4条边：（1,3）（1,2）（2,4）（2,3）
该图的拓扑序必须要满足以下两点：

1. 每个顶点只出现一次。
2. 对于图中的任何一条边，起点必须在终点之前。

拓扑序的求法

首先，不是所有的有向图都是有拓扑序的，只有有向无环图才有拓扑序，所以有向无环图又被称为拓扑图。

拓扑序是按照点的先后顺序排列的，也就是说入度为0的点一定是排在前面的，我们直接对一个图BFS一遍，BFS过程中更新每个点的入度，如果一个点的入度为0，那么就将其加入拓扑序，并且删除其与后继结点的所有边。

在读入边的时候，直接计算点的入度。

代码：

import java.io.*;
import java.util.*;

public class Main{
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static final int N = 100010;
	static int n, m, idx = 1;
	static int e[] = new int[N];
	static int ne[] = new int[N];
	static int h[] = new int[N];
	static int d[] = new int[N];
	static Queue<Integer> q = new LinkedList<>();
	static Queue<Integer> ans = new LinkedList<>();
	public static int Int(String s){return Integer.parseInt(s);}
	
	public static void add(int a, int b){
		e[idx] = b;
		ne[idx] = h[a];
		h[a] = idx++;
	}
	
	public static Boolean bfs(){
		while(!q.isEmpty()){
			int x = q.peek();
			q.poll();
			for(int i = h[x]; i != 0; i = ne[i]){ // 遍历所有后继结点
				if(--d[e[i]] == 0){// 删除当前点与后继结点的边，如果删除后
				                   //其后继结点的入度变为0，就入队
					q.add(e[i]);
					ans.add(e[i]);
				}
			}
		}
		if(ans.size() == n) return true;
		else return false;
	}
	
	public static void main(String[] args) throws IOException{
		String[] s = in.readLine().split(" ");
		n = Int(s[0]);
		m = Int(s[1]);
		
		for(int i = 0; i < m; i++){
			String s1[] = in.readLine().split(" ");
			add(Int(s1[0]), Int(s1[1]));
			
			d[Int(s1[1])] ++; // 入度加一  
		}
		
		int flag = 0;
		for(int i = 1; i <= n; i++){
			if(d[i] == 0){ // 找到入度为0的点
				q.add(i);
				ans.add(i);
				flag = 1;
			}
		}
		
		if(flag == 0)
			out.write("-1\n");
		else
		{
			if(bfs()){ // 输出拓扑序
				while(!ans.isEmpty()){
					out.write(ans.poll()+" ");
				}
			}
			else{ // 不存在拓扑序
			    out.write("-1\n");
			}
		}
		
		out.flush();
	}
}