### 思路
1. **建模问题**:将课程和依赖关系建模为有向图,其中课程是节点,依赖关系是有向边。
2. **选择算法**:使用拓扑排序算法来确定课程的学习顺序。由于需要确保输出唯一性,同等条件下编号小的课程排在前面,可以使用优先队列(最小堆)来实现。
3. **初始化**:创建一个入度数组来记录每个节点的入度,并创建一个优先队列来存储入度为0的节点。
4. **更新节点**:从优先队列中取出当前入度为0的节点,将其加入结果序列,并更新其邻接节点的入度。如果邻接节点的入度变为0,将其加入优先队列。
5. **终止条件**:当优先队列为空时,输出结果序列。
### 伪代码
```
function topological_sort(n, m, edges):
create an array in_degree of size n+1, initialized to 0
create a graph as an adjacency list of size n+1
create a priority queue pq
create a list result
for each (a, b) in edges:
graph[a].append(b)
in_degree[b] += 1
for i from 1 to n:
if in_degree[i] == 0:
pq.push(i)
while pq is not empty:
u = pq.pop()
result.append(u)
for each v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
pq.push(v)
return result
```
### C++代码
#include <iostream>
#include <vector>
#include <queue>using namespace std;vector<int> topological_sort(int n, int m, vector<pair<int, int>>& edges) {vector<int> in_degree(n + 1, 0);vector<vector<int>> graph(n + 1);priority_queue<int, vector<int>, greater<int>> pq;vector<int> result;for (const auto& edge : edges) {int a = edge.first;int b = edge.second;graph[a].push_back(b);in_degree[b] += 1;}for (int i = 1; i <= n; ++i) {if (in_degree[i] == 0) {pq.push(i);}}while (!pq.empty()) {int u = pq.top();pq.pop();result.push_back(u);for (int v : graph[u]) {in_degree[v] -= 1;if (in_degree[v] == 0) {pq.push(v);}}}return result;
}int main() {int n, m;cin >> n >> m;vector<pair<int, int>> edges(m);for (int i = 0; i < m; ++i) {int a, b;cin >> a >> b;edges[i] = {a, b};}vector<int> result = topological_sort(n, m, edges);for (int course : result) {cout << course << " ";}cout << endl;return 0;
}
### 总结
1. **问题建模**:将课程和依赖关系建模为有向图,使用拓扑排序算法求解课程学习顺序。
2. **算法选择**:使用拓扑排序算法,利用优先队列(最小堆)确保输出唯一性。
3. **实现细节**:初始化入度数组和优先队列,逐步更新节点的入度并维护优先队列。
4. **终止条件**:当优先队列为空时,输出结果序列。