62 lines
1.5 KiB
C++
62 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
|
||
*/
|
||
|
||
//本代码功能：以dfs输出一个有向无环图DAG的拓扑序
|
||
const int N = 1010;
|
||
|
||
bool st[N]; //标识是不是已经使用过
|
||
vector<int> edge[N]; //邻接表
|
||
vector<int> res; //拓扑序列
|
||
|
||
/**
|
||
* 功能：深度优先搜索，记录拓扑序
|
||
* @param u
|
||
*/
|
||
void dfs(int u) {
|
||
//如果访问过了，则返回，不再重复访问
|
||
if (st[u])return;
|
||
//标识u结点已使用
|
||
st[u] = true;
|
||
|
||
//遍历每个出边,找到下一组结点
|
||
for (int v:edge[u]) if (!st[v]) dfs(v);
|
||
|
||
//这一层完毕才把它自己扔进去,最后扔等于最先输出，因为后面是倒序输出的
|
||
res.push_back(u);
|
||
}
|
||
|
||
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);
|
||
}
|
||
//将所有结点进行深入优先搜索
|
||
for (int i = 1; i <= n; i++) dfs(i);
|
||
|
||
//输出，从后向前输出
|
||
for (int i = res.size() - 1; i >= 0; i--)
|
||
cout << res[i] << " ";
|
||
}
|