字典序最小拓扑排序C++模版
时间: 2023-08-27 08:22:44 浏览: 55
以下是一个用C++实现的拓扑排序的模板:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> topologicalSort(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> inDegree(n, 0);
for (int i = 0; i < n; i++) {
for (int j : graph[i]) {
inDegree[j]++;
}
}
vector<int> result;
queue<int> q;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int curr = q.front();
q.pop();
result.push_back(curr);
for (int next : graph[curr]) {
inDegree[next]--;
if (inDegree[next] == 0) {
q.push(next);
}
}
}
return result;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
vector<int> sorted = topologicalSort(graph);
for (int node : sorted) {
cout << node << " ";
}
cout << endl;
return 0;
}
```
这个模板使用邻接表表示有向图,通过计算每个节点的入度,然后利用队列进行拓扑排序。输出结果即为字典序最小的拓扑排序序列。输入部分需要提供节点数目n和边数目m,然后依次输入每一条边的起始节点u和终止节点v。输出结果为拓扑排序的节点序列。