算法基础课笔记整理

定义

拓扑序列是指在一个有向无环图（DAG）中，所有顶点的线性序列，满足以下两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，则在序列中顶点 A 出现在顶点 B 的前面。

例如，对于下面的一个图， $ 1~~2~~3 $ 就是一种拓扑序。

构建方法

先找到所以入度为 $0$ 的点，将其全部插入答案中。然后进行DFS，每次遍历到一个点就将这个点的入度减 $1$ ，当一个点的入度为 $0$ 时将其插入答案。

例题

AcWing 848. 有向图的拓扑序列

给定一个 $n$ 个点 $m$ 条边的有向图，点的编号是 $1$ 到 $n$，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 $-1$。

若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x, y)$，$x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示存在一条从点 $x$ 到点 $y$ 的有向边 $(x, y)$。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 $-1$。

数据范围

$1 \le n,m \le 10^5$

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int q[N], d[N], n, m;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;

    return;
}

bool topSort() {
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++) {
        if (d[i] == 0) q[++ tt] = i;
    }

    while (hh <= tt) {
        int t = q[hh ++];

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] --;

            if (d[j] == 0) q[++ tt] = j;
        }
    }

    return tt == n - 1;
}

int main() {
    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()) {
        for (int i = 0; i < n; i ++) cout << q[i] << ' ';
    } else {
        cout << "-1" << endl;
    }

    return 0;
}