1 /**\
2 拓扑排序:每次找到入度为0的点删掉
3 判断一个有向图中是否有环，无环的图都能进行拓扑排序
4 \**/
5 #include
6
7 using namespace std;
8
9 const int N = 1e5 + 10;
10
11 int inr[N]; //记录入度的数组
12 struct node
13 {
14 int t, next;
15 } e[N << 1];
16 int cnt = 0;
17 int head[N];
18 int n, m;
19
20 void add_edge(int x, int y)
21 {
22 e[++cnt].t = y;
23 e[cnt].next = head[x];
24 head[x] = cnt;
25 }
26
27 void topo()
28 {
29 queue<int> q;
30 for(int i = 1; i <= n; ++i)
31 {
32 if(inr[i] == 0) q.push(i);
33 }
34 int idx = 0, ans[N];
35 while(!q.empty())
36 {
37 int x = q.front();
38 ans[++idx] = x;
39 q.pop();
40 for(int i = head[x]; i != -1; i = e[i].next)
41 {
42 inr[e[i].t]--;
43 if(inr[e[i].t] == 0) q.push(e[i].t);
44 }
45 }
46 if(idx != n) cout << -1;
47 else
48 {
49 for(int i = 1; i <= idx; ++i) cout << ans[i] << " ";
50 }
51 }
52
53 signed main()
54 {
55 scanf("%d %d", &n, &m);
56 memset(head, -1, sizeof head);
57 for(int i = 1; i <= m; ++i)
58 {
59 int x, y;
60 scanf("%d %d", &x, &y);
61 inr[y]++;
62 add_edge(x, y);
63 }
64 topo();
65 return 0;
66 }
67 /*
68 6 8
69 1 2
70 1 4
71 1 3
72 2 4
73 3 4
74 5 3
75 5 4
76 6 4
77 */