4-拓扑排序

算法思想

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    static int[] h = new int[N],
        d = new int[N],
        e = new int[N],
        ne = new int[N];
    static int idx = 0;
    static int n;

    static Queue<Integer> ans = new LinkedList<>();

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        Arrays.fill(h, -1);

        while(m -- > 0)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a, b);
            // 第 b 个节点的入度
            d[b] ++;
        }

        if(topsort())
        {
            for(int i : ans)
                System.out.print(i + " ");
        }
        else System.out.println(-1);
    }

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

    public static boolean topsort()
    {
        Queue<Integer> q = new LinkedList<>();
		// 将入度为0的节点加入队列
        for(int i = 1; i <= n; i ++)
            if(d[i] == 0) q.offer(i);

        int number = 0;

        while(!q.isEmpty())
        {
            int t = q.poll();

            number ++;
            ans.offer(t);

            for(int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                if(-- d[j] == 0)
                {
                    q.offer(j);
                }
            }
        }
		// 所有的节点均已入队，说明存在拓扑排序
        return n == number;
    }
}