#include using namespace std; const int N = 1e5 + 10, M = N << 1; // AcWing 848. 有向图的拓扑序列 //邻接表 int e[M], h[N], idx, ne[M]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } /* 0代表未访问 1代表是这一阶段正在访问的(这一阶段指的是两个元素在同一个递归中) 2代表访问完毕 */ int color[N]; vector res; //拓扑序结果数组 bool dfs(int u) { color[u] = 1; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (color[j] == 1) return true; if (color[j] == 0 && dfs(j)) return true; } color[u] = 2; //利用递归的规则,在把自己为出发点的一组节点跑完,才把自己加入路径,它的孩子在它之前已经加入了路径 res.push_back(u); return false; } 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); } bool flag = false; for (int i = 1; i <= n; i++) if (!color[i]) { flag = dfs(i); //枚举每个点,如果没有访问过,就作为起点搜索 if (flag) break; } if (flag) puts("-1"); else { 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 这是有问题的~,需要新方法判环~ */