【记录 | 模板题】链式前向星 + 拓扑排序 + 小根堆实现结果字典序最小

拓扑排序

拓扑排序是针对有向无环图（DAG）的一种排序算法。它的主要思想是将有向无环图的顶点按照顶点的先后关系进行排序。

拓扑排序的算法步骤如下：

1. 从DAG图中选择一个没有前驱（即入度为0）的顶点并输出。

2. 从图中删除该顶点和所有以它为起点的有向边。

3. 重复步骤1和2，直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

注意：拓扑排序的结果可能不是唯一的，因为可能存在多个无前驱的顶点，同样，一个顶点可能被多个其他顶点指向。

拓扑排序常用于任务调度、课程安排等需要处理依赖关系的场景。例如，如果任务A依赖于任务B，那么在拓扑排序中，任务B应该排在任务A之前。

下面，我们来看这道模板题。

【模板题】拓扑排序

题目描述

有向无环图上有n个点，m条边。求这张图字典序最小的拓扑排序的结果。字典序最小指希望排好序的结果中，比较靠前的数字尽可能小。

输入格式

第一行是用空格隔开的两个整数n和m，表示n个点和m条边。

接下来是m行，每行用空格隔开的两个数u和v，表示有一条从u到v的边。

输出格式

输出一行，拓扑排序的结果，数字之间用空格隔开

样例 #1

样例输入 #1

5 3
1 2
2 4
4 3

样例输出 #1

1 2 4 3 5

提示

$1\le n,m\le 10^5$

注意：图上可能有重边。

参考代码

这是一道拓扑排序的模板题，我们使用链式前向星来存储图，使用小根堆来获取字典序最小的拓扑排序。

topoSort 函数是实现拓扑排序的核心函数，它首先将所有入度为0的节点添加到小根堆中，然后不断从小根堆中弹出最小元素并将其添加到结果数组中，同时更新其邻接节点的入度，如果邻接节点的入度变为0，则将其添加到小根堆中。这个过程一直持续到小根堆为空为止。

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
   

    // 定义最大节点和边的数量
    public static int MAXN = 100001;
    public static int MAXM = 100001;

    // 使用链式前向星存储图
    public static int[] head = new int[