You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
64 lines
1.4 KiB
64 lines
1.4 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e5 + 10, M = N << 1;
|
|
// AcWing 848. 有向图的拓扑序列
|
|
// 不考虑环，只能过 11/14个测试点~
|
|
|
|
//邻接表
|
|
int e[M], h[N], idx, ne[M];
|
|
void add(int a, int b) {
|
|
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
|
|
}
|
|
|
|
bool st[N];
|
|
vector<int> res;
|
|
|
|
void dfs(int u) {
|
|
st[u] = true; //标识已走过
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
int j = e[i];
|
|
if (!st[j]) dfs(j); //如果目标节点未走过
|
|
}
|
|
//利用递归的规则，在把自己为出发点的一组节点跑完，才把自己加入路径，它的孩子在它之前已经加入了路径
|
|
res.push_back(u);
|
|
}
|
|
|
|
int main() {
|
|
memset(h, -1, sizeof h);
|
|
int n, m;
|
|
cin >> n >> m;
|
|
|
|
for (int i = 1; i <= m; i++) {
|
|
int a, b;
|
|
cin >> a >> b;
|
|
add(a, b);
|
|
}
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
if (!st[i]) dfs(i); //枚举每个点，如果没有访问过，就作为起点搜索
|
|
|
|
reverse(res.begin(), res.end());
|
|
|
|
for (int i = 0; i < res.size(); i++)
|
|
printf("%d%c", res[i], i == res.size() - 1 ? '\n' : ' ');
|
|
return 0;
|
|
}
|
|
/*
|
|
无环测试用例:
|
|
3 3
|
|
1 2
|
|
2 3
|
|
1 3
|
|
答案:
|
|
1 2 3
|
|
|
|
|
|
有环测试用例：
|
|
3 3
|
|
1 2
|
|
2 3
|
|
3 1
|
|
答案:应该输出有环，-1
|
|
实际： 1 2 3
|
|
这是有问题的~,需要新方法判环~
|
|
*/ |