拓扑排序

拓扑图(DAG)，也叫有向无环图
步骤：
统计每个节点的入度
将所有入度为0的节点入队
bfs，更新节点的入度，并更新队列

848. 有向图的拓扑序列

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y之前，则称 A是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y的有向边 (x,y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1。
数据范围
1≤n,m≤105
输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

思路

用邻接表存储数据，在读入数据时顺便统计每个节点的入度
入度为0的点入队，用队列中的元素更新其它节点的入度！
妙就妙在最后队列中存储的正好是结果！

import java.util.*;
public class Main {
    static int n, m, idx, hh, tt;
    static int[] h, e, ne, q, d;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        h = new int[n + 1];
        Arrays.fill(h, -1);
        e = new int[m];
        ne = new int[m];
        q = new int[n + 1];
        d = new int[n + 1];
        hh = 0;
        tt = -1;
        while (m-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt();
            d[b] += 1;
            add(a, b);
        }
        boolean flag = bfs();
        if (!flag) System.out.println(-1);
        else {
            for (int i = 0; i < n; i++) {
                System.out.print(q[i] + " ");
            }
        }
    }
    static boolean bfs() {
        for (int i = 1; i <= n; i++) {
            if (d[i] == 0) q[++tt] = i;
        }
        while (hh <= tt) {
            int cur = q[hh++];
            for (int i = h[cur]; i != -1; i = ne[i]) {
                int j = e[i];
                d[j]--;
                if (d[j] == 0) {
                    q[++tt] = j;
                }
            }
        }
        if (tt == n - 1) return true;
        else return false;
    }
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

应用

最长路

AcWing 1192. 奖金

:::info 总结：差分约束问题求最长路(最短路分析类似)

1. 边权无限制 spfa O(nm) 有解的充要条件是无正环
2. 边权非负 tarjan O(n + m) 有解的充要条件是强连通分量边权均为0
3. 边权为正 拓扑排序 O(n + m) 有解的充要条件是拓扑排序有解 :::

可达性

AcWing 164. 可达性统计
结合BitSet

建边优化

AcWing 456. 车站分级
如果是建n2条边