拓扑排序

拓扑排序

​ 在计算机科学领域，有向图的拓扑排序或拓扑测序是对其顶点的一种线性排序，使得对于从顶点u到顶点v的每个有向边uv，u在排序中都在v之前。

​ 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。

​ 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。

​ 任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内，构建任何有向无环图的拓扑排序。

​ 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序（英语：Topological sorting）：

1. 序列中包含每个顶点，且每个顶点只出现一次；
2. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

例题：

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围

1≤n,m≤10^5

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = (int)1e5 + 10;
    static int idx = 0;
    static int n, m;
    static int h[] = new int[N];
    static int e[] = new int[N];
    static int ne[] = new int[N];
    static int d[] = new int[N];
    static int q[] = new int[N];
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bufferedReader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        Arrays.fill(h, -1);

        while (m -- > 0){
            String[] s1 = bufferedReader.readLine().split(" ");
            int x = Integer.parseInt(s1[0]);
            int y = Integer.parseInt(s1[1]);
            add(x, y);
            d[y] ++;
        }

        if (toSort()){
            for (int i = 0; i < n; i++) {
                System.out.print(q[i] + " ");
            }
        }else System.out.println(-1);

        bufferedReader.close();
    }

    private static boolean toSort(){
        int hh = 0,tt = -1;
        for (int i = 1; i <= n; i++) {
            if (d[i] == 0) q[++ tt] = i;
        }
        while (hh <= tt){
            int t = q[hh ++];
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                d[j] --;
                if (d[j] == 0) q[++ tt] = j;
            }
        }
        return n - 1 == tt;
    }

    private static void add(int x, int y){
        e[idx] = y;
        ne[idx] = h[x];
        h[x] = idx ++;
    }
}