3、有向图拓扑排序（宽搜）

AcWing 848. 有向图的拓扑序列

有向图的拓扑排序 找到入度为0的点，广度优先入队，输出即可

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.kuansou();
    }

    int n, m;
    int N = 200010;
    int[] e = new int[N];
    int[] ne = new int[N];
    int[] h = new int[N];//head指针
    int[] d = new int[N];//结点的入度
    int[] queue = new int[N];
    //e[h[a]]存储的是a的拉链头结点的结点值
    int idx = 1;

    void insert(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }


    boolean bfs() {
        int hh = 0, tt = -1;
        for (int i = 1; i <= n; i++) if (d[i] == 0) queue[++tt] = i;
        while(hh<=tt){//队列非空
            int item=queue[hh++];
            for(int i=h[item];i!=-1;i=ne[i]){
                if(d[e[i]]!=0) d[e[i]]--;
                if(d[e[i]]==0){
                    queue[++tt]=e[i];
                }
            }
        }
        return tt==n-1;
    }

    void kuansou() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            insert(a, b);
            d[b]++;
        }
        if (bfs()) {
            for (int i = 0; i < n; i++) {
                System.out.print(queue[i]+" ");
            }
        } else {
            System.out.println("-1");
        }
    }
}