#include using namespace std; const int N = 100010; int n, m; // 点数,边数 int d[N]; // d[N]:入度,所有入度为零的点,可以排在当前最前面的位置。 // 树和图的存储 int h[N], e[N], ne[N], idx; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } // 拓扑 int q[N]; bool topsort() { // 初始化队列 int hh = 0, tt = -1; // 扫描所有入度为零的点入队列 for (int i = 1; i <= n; i++) if (!d[i]) q[++tt] = i; // 广度遍历 while (hh <= tt) { int t = q[hh++]; // 队列头 for (int i = h[t]; ~i; i = ne[i]) { // 遍历t的所有出边 int j = e[i]; if (--d[j] == 0) // 入度减1后,是不是为0 (前序依赖为0) q[++tt] = j; // 为0则入队列 } } cout << tt << endl; // 如果一共n个结点进入过队列,则表示存在拓扑序 return tt == n - 1; } /* 4 4 1 2 2 3 3 4 4 2 */ int main() { // 初始化为-1 memset(h, -1, sizeof h); cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; add(a, b); d[b]++; // 记录每个结点的入度 } if (!topsort()) puts("-1"); else { // 队列次序其实就是拓扑序,这里就充分体现了利用数组模拟队列的优势,queue就麻烦了。 for (int i = 0; i < n; i++) printf("%d ", q[i]); puts(""); // 有向无环图的拓扑序是不唯一的 } return 0; }