$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
无向图没有拓扑序列。
拓扑序列存在于有向无环图，又称$DAG$图、拓扑图。
拓扑排序满足：每条边$(x,y)$，$x$在序列中都在$y$前面。
先引入度数的概念：

• 度数=入度+出度
  • 入度：有多少条边指向自己。
  • 出度：有多少条边从自己指出。

因此入度为$0$的点可以作为源点（不会有边在它前面），每次删去队头和连接它的所有边。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N;
int n, m;
int h[N], e[M], ne[M], idx;
int d[N];  //入度
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort() {
    queue<int> q;
    int ans[N], top = 0;
    for (int i = 1; i <= n; i++)
        if (!d[i]) q.push(i), ans[++top] = i;
    while (q.size()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i ; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q.push(j), ans[++top] = j;
        }
    }
    if (top != n) puts("-1");
    else for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}


int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b); d[b]++;
    }
    topsort();
    return 0;
}