56 lines
1.5 KiB
C++
56 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
//拓扑排序有两种方式，就是bfs和dfs,一般书中介绍的大多数是bfs,大家就以为拓扑排序只有一种办法，其实是不对的。
|
||
//参考链接 ：https://blog.csdn.net/weixin_43918531/article/details/86740991
|
||
/**
|
||
5 4
|
||
|
||
1 2
|
||
2 3
|
||
2 5
|
||
3 4
|
||
|
||
参考答案：
|
||
1 2 5 3 4
|
||
*/
|
||
|
||
//本代码功能：以bfs输出一个有向无环图DAG的拓扑序
|
||
const int N = 1010;
|
||
vector<int> edge[N]; //邻接表
|
||
int ind[N]; //入度数组
|
||
queue<int> q; //队列
|
||
|
||
int n; //n个结点
|
||
int m; //m条边
|
||
int main() {
|
||
//读入，建图
|
||
cin >> n >> m;
|
||
for (int i = 1; i <= m; i++) {
|
||
int x, y;
|
||
cin >> x >> y;
|
||
edge[x].push_back(y);
|
||
ind[y]++;//维护入度
|
||
}
|
||
//入度为零的放入队列
|
||
for (int i = 1; i <= n; i++) if (!ind[i]) q.push(i);
|
||
|
||
//广度优先搜索DAG，就是拓扑排序的模板
|
||
while (!q.empty()) {
|
||
int x = q.front();
|
||
q.pop();
|
||
//输出拓扑序
|
||
cout << x << " ";
|
||
for (int i = 0; i < edge[x].size(); i++) { //遍历所有出边
|
||
int y = edge[x][i]; //目标结点
|
||
//对接点入度-1，抹去这条入边
|
||
ind[y]--;
|
||
//如果入度为0，则入队列，准备处理它
|
||
if (!ind[y]) q.push(y);
|
||
}
|
||
}
|
||
return 0;
|
||
}
|