acwing算法基础之搜索与图论--有向图的拓扑序列

1 基础知识

拓扑序列：针对有向图而言，该序列内，所有边都是从前指向后的。

如果存在环，那么该图一定不存在拓扑序列。否则，一定存在拓扑序列。

有向图中的入度和出度。
入度为0的结点，可以作为拓扑序列的起点。

求拓扑序列的关键步骤：

1. 把入度为0的结点插入队列q。
2. 弹出队头t，遍历队头t的下一个结点，将其入度减1。操作之后，如果其值为0，则插入队列q。
3. 重复进行步骤2，直至队列q为空。

2 模板

题目1：给出结点数目n和边数m，以及一系列的边，如果此图存在拓扑序列，请输出（输出任意一种拓扑序列即可）；否则，输出-1。

#include <iostream>
#include <vector>
#include <queue>using namespace std;const int N = 1e5 + 10;
int n, m;
vector<vector<int>> g(N);
vector<int> d(N); //存储每个结点的入度int main() {cin >> n >> m;int x, y;while (m--) {cin >> x >> y;//添加x到y的边g[x].emplace_back(y);d[y]++;}queue<int> q;for (int i = 1; i <= n; ++i) {if (d[i] == 0) {q.push(i);}}vector<int> res;while (!q.empty()) {auto t = q.front();res.emplace_back(t); //存入向量res中 q.pop();//t可以走到哪里for (auto x : g[t]) {//把结点t删除d[x]--;if (d[x] == 0) {q.push(x);}}}if (res.size() == n) {for (int i = 0; i < n; ++i) cout << res[i] << ' ';cout << endl;} else {puts("-1");}return 0;
}

3 工程化

暂无。。。