【题目来源】
AtCoder：D - Course Enrollment Order
【题目描述】
Takahashi is trying to take all \(N\) courses at his university.
高桥正在尝试修读他大学的所有 \(N\) 门课程。
The courses are numbered from \(1\) to \(N\), and each course is taken exactly once. Some courses have prerequisite courses, and in order to take such a course, all of its prerequisite courses must have been completed beforehand. A single course may have multiple prerequisites. Courses with no prerequisites can be taken from the beginning.
课程编号从 \(1\) 到 \(N\)，每门课程恰好修读一次。有些课程有先修课程，为了修读这样的课程，其所有先修课程必须已经完成。一门课程可能有多个先修课程。没有先修课程的课程可以从一开始就修读。
There are \(M\) prerequisite relationships given, each in the form: "In order to take course \(B_j\), course \(A_j\) must have been completed first."
给出了 \(M\) 个先修关系，每个关系形式如下："为了修读课程 \(B_j\)，必须先完成课程 \(A_j\)。"
Takahashi takes courses one at a time. At each step, among the courses he has not yet taken whose prerequisites have all been completed (these are called available courses), he selects the one with the smallest number and takes it.
高桥一次修读一门课程。在每一步，在所有尚未修读且其先修课程已全部完成的课程中（这些课程称为可选课程），他选择编号最小的那一门进行修读。
Output the order in which Takahashi takes all the courses.
输出高桥修读所有课程的顺序。
It is guaranteed that there are no contradictions in the prerequisite relationships (i.e., no cycles exist), and that it is always possible to take all courses. Furthermore, the above rule uniquely determines the order of enrollment.
保证先修关系中没有矛盾（即不存在循环），并且始终可以修完所有课程。此外，上述规则唯一确定了选课顺序
【输入】
\(N\) \(M\)
\(A_1\) \(B_1\)
\(A_2\) \(B_2\)
\(\vdots\)
\(A_M\) \(B_M\)
- The first line contains an integer \(N\) representing the number of courses and an integer \(M\) representing the number of prerequisite relationships, separated by a space.
- The \(j\)-th of the following \(M\) lines \((1 \leq j \leq M)\) contains integers \(A_j\) and \(B_j\) separated by a space, indicating that course \(A_j\) must be completed before taking course \(B_j\).
【输出】
Output the order in which Takahashi takes the courses on a single line, separated by spaces. That is, output \(N\) integers arranged from left to right in the order they are taken.
【输入样例】
4 3
1 2
3 4
2 4
【输出样例】
1 2 3 4
【核心思想】
-
问题分析：给定有向无环图（DAG），需要输出一个拓扑序列，使得序列的字典序最小。普通队列实现的拓扑排序只能保证得到一个合法序列，但无法保证字典序最小。
-
算法选择：
- Kahn算法：基于入度的拓扑排序算法
- 优先队列（最小堆）：每次从入度为 \(0\) 的节点中选择编号最小的，保证字典序
-
关键步骤：
- 初始化入度数组 \(in[v]\) 和邻接表
- 将所有入度为 \(0\) 的节点加入优先队列（最小堆）
- 循环取出队首最小元素 \(u\)，加入拓扑序列
- 遍历该节点的所有出边，减少邻接点 \(v\) 的入度 \(in[v]\)
- 若邻接点入度变为 \(0\)，加入优先队列
- 最终输出拓扑序列
-
时间/空间复杂度：
- 时间复杂度：\(O((N + M) \log N)\)，每个节点和边处理一次，优先队列操作 \(O(\log N)\)
- 空间复杂度：\(O(N + M)\)，邻接表、入度数组和队列
-
字典序拓扑排序的核心思想：
- 普通队列：先进先出，拓扑序列不唯一
- 优先队列：每次选择最小可用节点，保证字典序最小
- 适用于需要最小/最大字典序拓扑序列的场景
【算法标签】
拓扑排序
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = 200005;int n, m;
// 优先队列（最小堆），用于实现字典序最小的拓扑排序
priority_queue<int, vector<int>, greater<int> > q;
// 存储拓扑排序的序列
vector<int> seq;
// 入度数组
int ind[N];
// 邻接表（数组模拟链表）
int h[N], e[M], ne[M], idx;// 添加有向边 a -> b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}int main()
{cin >> n >> m;// 初始化邻接表头指针memset(h, -1, sizeof(h));for (int i = 1; i <= m; i++){int a, b;cin >> a >> b;add(a, b);// 增加终点 b 的入度ind[b]++;}// 将所有入度为 0 的顶点加入优先队列for (int i = 1; i <= n; i++){if (ind[i] == 0){q.push(i);}}while (!q.empty()){// 取出当前编号最小的入度为 0 的顶点int u = q.top();q.pop();// 将该顶点加入拓扑序列seq.push_back(u);// 遍历顶点 u 的所有出边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];// 减少后继顶点的入度ind[j]--;// 如果入度变为 0，则加入优先队列if (ind[j] == 0){q.push(j);}}}// 输出拓扑排序的结果for (int i = 0; i < seq.size(); i++){cout << seq[i] << " ";}cout << endl;return 0;
}
【运行结果】
4 3
1 2
3 4
2 4
1 2 3 4