说明

此文仅为作者复习所用，无教程作用。

介绍

在图论中，拓扑排序（Topological Sorting）是一种针对有向无环图（DAG, Directed Acyclic Graph）的线性排序算法，其核心作用是确定图中节点的依赖顺序，使得所有边的方向在排序中保持一致。

使用

找环如果在拓扑排序过程中无法包含所有节点（即剩余节点的入度均不为0），说明图中存在环
最值问题/动态规划在DAG上按拓扑序处理节点，可以高效计算最长路径、最短路径或依赖相关的动态规划问题。

常用算法 Kahn (基于入度的类bfs)

初始化一个队列，将所有入度为0的节点加入队列。
依次取出队首节点，删除其所有出边（即相邻节点的入度减1），若相邻节点入度变为0则入队。
若最终排序的节点数等于图中总节点数，则排序成功；否则说明有环

存图方式

邻接表或链式前向星

1.最大食物链计数普及/提高-

~~开胃小菜~~

题目描述

原题链接：https://www.luogu.com.cn/problem/P4017给你一个食物网，你要求出这个食物网中最大食物链的数量。（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）Delia 非常急，所以你只有 $1$ 秒的时间。由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。
输入：第一行，两个正整数 $n 、 m$ ，表示生物种类 $n$ 和吃与被吃的关系数 $m$ 。接下来 $m$ 行，每行两个正整数，表示被吃的生物A和吃A的生物B。
输出：
一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

示例

输入：
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
输出：
5

思路

拓扑排序的经典题目，bfs存入度为0的点每次删点将权值赋给下一个点即可。链式前向星/邻接表时间复杂度O(n + m)

代码

链式前向星

const int N = 1e6 + 10 , mod = 80112002;
int e[N] , ne[N] , h[N] , idx;
int in[N] , out[N];
int n , m;
int value[N];
int ans = 0;

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

void bfs()
{
    queue<int> q;
    for (int i = 1 ; i <= n ; i ++ )
        if (!in[i]) q.push(i) , value[i] = 1;
    
    while (q.size())
    {
        int index = q.front();
        q.pop();

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];
            in[j] --;

            value[j] = (value[j] + value[index]) % mod;

            if (!in[j]) q.push(j);
        }
    }

    for (int i = 1 ; i <= n ; i ++ )
    {
        if (!out[i])
            ans = (ans + value[i]) % mod; 
    }
    return ;

}

void solve()
{
    memset(h , -1 , sizeof h);
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++ )
    {
        int a , b;
        cin >> a >> b;
        add(a , b);
        out[a] ++ , in[b] ++;
    }

    bfs();

    cout << ans << endl;
}

邻接表

const int N = 1e6 + 10 , mod = 80112002;
vector<int> g[N];
int in[N] , out[N];
int n , m;
int value[N];
int ans = 0;

void bfs()
{
    queue<int> q;
    for (int i = 1 ; i <= n ; i ++ )
        if (!in[i]) q.push(i) , value[i] = 1;
    
    while (q.size())
    {
        int index = q.front();
        q.pop();

        int l = g[index].size();
        for (int i = 0 ; i < l ; i ++ )
        {
            int v = g[index][i];

            in[v] --;
            value[v] = (value[v] + value[index]) % mod;

            if (!in[v])
                q.push(v);
        }
    }

    for (int i = 1 ; i <= n ; i ++ )
    {
        if (!out[i]) ans = (ans + value[i]) % mod;
    }
}

2.摄像头普及/提高-

题目描述

原题链接：https://www.luogu.com.cn/problem/P2712

食品店里有 $n$ 个摄像头，这种摄像头很笨拙，只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店，为了不让摄像头拍下他们犯罪的证据，他们抢劫前的第一件事就是砸毁这些摄像头。为了便于砸毁摄像头，松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号，一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。
现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头，如不能则输出还没砸掉的摄像头的数量。
输入格式：第 $1$ 行，一个整数 $n$ ，表示摄像头的个数。第 $2$ 到 $n + 1$ 行是摄像头的信息，包括：摄像头的位置 $x$ ，以及这个摄像头可以监视到的位置数 $m$ ，之后 $m$ 个数 $y$ 是此摄像头可以监视到的位置。(砸了这些摄像头之后自然这些位置就监视不到了)
输出格式：若可以砸掉所有摄像头则输出“ $YES$ ”，否则输出还没砸掉的摄像头的数量。（不带引号）

示例

输入：
5
1 1 2
2 1 1
3 1 7
4 1 1
5 0
输出：
2

思路

每增加一个被监控的摄像头，其入度就+1，寻找入度为0的摄像头点位破坏掉(出队)并统计破坏数量。如果被破坏的数量nums 等于总数n，即可以全部破坏掉。此题中所监控的点位不一定有一个摄像头，所以需要用到set存摄像头的位置。满足有摄像头且入度为0才能入队。

代码

链式前向星

const int N = 1e5 + 10;
int e[N] , ne[N] , h[N] , idx;
int in[N] , out[N];
int nums;

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

void solve()
{
    memset(h , -1 , sizeof h);
    int n;
    cin >> n;
    set<int> se;
    for (int i = 1 ; i <= n ; i ++ )
    {
        int a , num;
        cin >> a >> num;
        se.insert(a);
        while (num -- )
        {
            int b;
            cin >> b;
            add(a , b);
            out[a] ++ , in[b] ++;
        }
    }

    queue<int> q;

    for (int i : se)
        if (!in[i]) q.push(i);
    while (q.size())
    {
        nums ++;
        int index = q.front();
        q.pop();

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];
            in[j] -- ;
            if (!in[j] && se.count(j)) q.push(j);
        }
    }

    if (n == nums) cout << "YES" << endl;
    else cout << n - nums << endl;
}

3.TimeLine G (USACO20FEB) 普及/提高-

原题链接：https://www.luogu.com.cn/problem/P6145

题目描述

Bessie 在过去的 $M$ 天内参加了 $N$ 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_{i}$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a, b, x)$ ，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。
现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。

保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：
1. 第 $i$ 次挤奶不早于第 $S_{i}$ 天进行，且不晚于第 $M$ 天进行；
2. 所有的记忆都得到满足；
输入格式：第一行三个整数 $N, M, C$ 。保证 $1 \leq N, C \leq 1 0^{5}$ ， $2 \leq M \leq 1 0^{9}$ 。接下来一行包含 $N$ 个整数 $S_{1}, S_{2}, \dots, S_{n}$ ，保证 $\forall1 \leq i \leq n$ ，都满足 $1 \leq S_{i} \leq M$ 。
下面 $C$ 行每行三个整数 $a, b, x$ ，描述一条记忆。保证 $a \neq = b$ ，且 $1 \leq x \leq M$ 。
输出格式：输出 $N$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 次挤奶的最早日期。

示例

输入：
4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4
输出：
1
6
3
8

思路

理解题意之后，得知有入度的奶牛是被限制了最小天数的，所以按照入度，从入度为0的奶牛以此计算最小的挤奶天数。提到s中为已知的最小天数，那么就需要求得每一只奶牛的上一只奶牛的限制的最大值，加上上一只奶牛的挤奶时间，和s中已知的最小天数限制比较，取max。时间复杂度O(nlogn).

代码

链式前向星

const int N = 1e6 + 10;
int e[N] , ne[N] , idx , h[N] , w[N];
int n , m , k;
int s[N];
int ans[N] , in[N] , out[N];

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

void bfs()
{
    queue<int> q;
    for (int i = 1 ; i <= n ; i ++ )
    {
        ans[i] = s[i];
        if (!in[i]) q.push(i);
    }
    while (q.size())
    {
        int index = q.front();
        q.pop();

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if (w[i] + ans[index] >= s[j])
            {
                s[j] = w[i] + ans[index];
                ans[j] = max(ans[j] , s[j]);
            }

            in[j] --;
            if (!in[j]) q.push(j);
        }
    }
}

void solve()
{
    memset(h , -1 , sizeof h);
    cin >> n >> m >> k;
    for (int i = 1 ; i <= n ; i ++ ) cin >> s[i];
    for (int i = 1 ; i <= k ; i ++ )
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c);
        out[a] ++ , in[b] ++;
    }

    bfs();

    for (int i = 1 ; i <= n ; i ++ )
        cout << ans[i] << endl;
}

4.旅行计划普及/提高-

原题链接：https://www.luogu.com.cn/problem/P1137

题目描述

小明要去一个国家旅游。这个国家有 N 个城市，编号为 1 至 N，并且有 M 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 i 停止。所以他就需要选择最先到达的城市，并制定一条路线以城市 i 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的 i，都需要你为小明制定一条路线，并求出以城市 i 为终点最多能够游览多少个城市
输入格式：第一行为两个正整数 N,M。接下来 M 行，每行两个正整数 x,y，表示了有一条连接城市 x 与城市 y 的道路，保证了城市 x 在城市 y 西面。
输出格式：N 行，第 i 行包含一个正整数，表示以第 i 个城市为终点最多能游览多少个城市。

示例

输入：
5 6
1 2
1 3
2 3
2 4
3 4
2 5
输出：
1
2
3
4
3
说明：均选择从城市1出发可以得到以上答案。

思路

选择入度0的城市为起点，依次记录走到每个城市的时候可以经过的最大城市数量(即每次入度为0的时候保证为最大)。时间复杂度：O(nlogn).

代码

链式前向星

const int N = 1e5 + 10 , M = 2 * N;
int h[N] , e[M] , ne[M] , idx;
int in[N];
int nums[N];
int n , m;

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

void bfs()
{
    queue<int> q;
    for (int i = 1 ; i <= n ; i ++ ) if (!in[i]) q.push(i) , nums[i] ++;

    while (q.size())
    {
        int index = q.front();
        q.pop();

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];
            in[j] --;

            if (!in[j])
            {
                nums[j] += nums[index] + 1;
                q.push(j);
            }
        }
    }
}


void solve()
{
    memset(h , -1 , sizeof h);
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++ )
    {
        int a , b;
        cin >> a >> b;
        add(a , b);
        in[b] ++;
    }

    bfs();

    for (int i = 1 ; i <= n ; i ++ ) cout << nums[i] << endl;
}