#include 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 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 这是有问题的~,需要新方法判环~ */