还不会拓扑排序？看这一篇就够了

news/2024/7/3 13:21:58 标签: 算法, 图论, 数据结构, c++, 拓扑排序

目录

一、什么是拓扑排序？

拓扑排序是一种有向无环图（DAG）的顶点排序方法，它将一个有向无环图中的所有顶点排成一个线性序列，使得图中任意一条有向边上的起点排在终点的前面。

这样说还不够具体，我们先来看一个例子。假设某大学的课程安排如下：

课程编号课程名称先修课程
1 1 1高等数学 − - −
2 2 2程序设计基础 − - −
3 3 3离散数学 1 ,   2 1,\,2 1,2
4 4 4数据结构 2 ,   3 2,\,3 2,3
5 5 5高级语言程序设计 2 2 2
6 6 6编译方法 4 ,   5 4,\,5 4,5
7 7 7操作系统 4 ,   9 4,\,9 4,9
8 8 8普通物理 1 1 1
9 9 9计算机原理 8 8 8

为了顺利修完这九门课程，我们必须安排一个合理的学习顺序。

首先根据以上表格构建一个有向图，即若 j j j 的先修课程有 i i i，则画一条 i i i 到 j j j 的有向边，于是可以得到：

一个合理的学习顺序是： 1 → 8 → 9 → 2 → 3 → 5 → 4 → 7 → 6 1\to8\to9\to2\to3\to5\to4\to7\to6 1→8→9→2→3→5→4→7→6，该序列又称拓扑序列，是对上述有向图进行拓扑排序后的结果。

可以看出，拓扑序列不唯一。例如， 1 → 8 → 9 → 2 → 3 → 5 → 4 → 6 → 7 1\to8\to9\to2\to3\to5\to4\to6\to7 1→8→9→2→3→5→4→6→7 也是满足要求的学习顺序。

此外还可以证明，DAG一定存在拓扑序列，存在拓扑序列的图也一定是DAG，因此DAG又被称为拓扑图。

二、拓扑排序的实现

拓扑排序的具体步骤如下：

  • 找到所有入度为 0 0 0 的顶点，并将其输出到拓扑序列中。
  • 将这些顶点从图中删除，并将所有以该顶点为起点的边的终点的入度减 1 1 1。
  • 不断重复以上两个操作，直到所有的顶点都被输出到拓扑序列中或者图中不存在入度为 0 0 0 的顶点为止。

代码实现：

int n, m;  // n表示节点数量，m表示边的数量
int h[N], e[N], ne[N], idx;  // 邻接表存图
int in[N];  // 保存每个点的入度
vector<int> L;  // 存储拓扑序列

// 拓扑排序算法
void topo_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
    	// 找到所有入度为0的点然后将其添加到队列中，同时也输出到拓扑序列中
        if (in[i] == 0) {
            q.push(i);
            L.push_back(i);
        }

    while (!q.empty()) {
        auto t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {  // 遍历t的所有相邻节点
            int j = e[i];
            in[j]--;  // 将相邻节点的入度-1
            // 如果相邻节点的入度减到0，则入队列，同时将其输出到拓扑序列中
            if (in[j] == 0) {
                q.push(j);
                L.push_back(i);
            }
        }
    }
}

如果 L.size() == n 成立，说明该图存在拓扑序列，否则说明该图不是DAG。

拓扑排序的时间复杂度和BFS相同，均为 O ( n + m ) O(n+m) O(n+m)。

2.1 拓扑排序模版

上述代码显得过于臃肿，我们可以进一步简化以形成模版（务必背过）。

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

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        L.push_back(t);

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

三、拓扑排序的应用

3.1 有向图的拓扑序列

🔗 原题链接：AcWing 848. 有向图的拓扑序列

直接套模板即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int in[N];
vector<int> L;

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

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

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        L.push_back(t);

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        add(x, y), in[y]++;
    }

    topo_sort();

    if (L.size() == n) {
        for (auto i: L) cout << i << ' ';
        cout << "\n";
    } else cout << -1 << "\n";

    return 0;
}

3.2 家谱树

🔗 原题链接：AcWing 1191. 家谱树

如果 b b b 是 a a a 的孩子，则画一条由 a a a 指向 b b b 的有向边，然后拓扑排序即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = N * N / 2;

int n;
int h[N], e[M], ne[M], idx;
int in[N];
vector<int> L;

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

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

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        L.push_back(t);

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(h, -1, sizeof h);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int x;
        while (cin >> x, x) {
            add(i, x);
            in[x]++;
        }
    }

    topo_sort();

    for (auto i: L) cout << i << ' ';
    cout << "\n";

    return 0;
}

3.3 奖金

🔗 原题链接：AcWing 1192. 奖金

对于建图，如果 b b b 的奖金比 a a a 高，则画一条 a a a 到 b b b 的有向边。

要使总奖金最少，很显然，初始时所有入度为 0 0 0 的点的奖金都为 100 100 100 元。之后，对于图中任意两点 x , y x,y x,y，如果存在 x x x 到 y y y 的有向边，那么 y y y 的奖金应当比 x x x 的奖金多一元。

我们可以让队列不止保存员工的编号，还保存每位员工的奖金，这样在遍历的时候就能够方便的去计算每位员工的奖金了。

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int in[N];
vector<int> L;

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

void topo_sort() {
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.emplace(i, 100);

    while (!q.empty()) {
        auto [t, bonus] = q.front();
        q.pop();
        L.push_back(bonus);

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (!--in[j]) q.emplace(j, bonus + 1);  // 多一元
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        add(y, x), in[x]++;
    }

    topo_sort();

    if (L.size() == n) cout << accumulate(L.begin(), L.end(), 0) << "\n";
    else cout << "Poor Xed\n";

    return 0;
}

3.4 可达性统计

🔗 原题链接：AcWing 164. 可达性统计

本题可以用BFS暴力求解，时间复杂度为 O ( n ( n + m ) ) ≈ 1.8 × 1 0 9 O(n(n+m))\approx1.8\times 10^9 O(n(n+m))≈1.8×109，只能过 3 / 5 3/5 3/5 的测试点。

不妨设从 x x x 出发能够到达的点的集合为 f ( x ) f(x) f(x)，易知

f ( x ) = { x } ∪ ⋃ y ∈ N ( x ) f ( y ) f(x)=\{x\}\cup \bigcup_{y\in N(x)} f(y) f(x)={x}∪y∈N(x)⋃​f(y)

也就是说，从 x x x 出发能够到达的点的集合为从「 x x x 的各个后继节点」出发能够到达的点的集合的并集再加上 x x x 自身。所以，只有在计算出一个点的所有后继节点的 f f f 值之后，我们才能够算出该点的 f f f 值。这启发我们先对图进行拓扑排序得到一个拓扑序列，然后再倒序计算。

我们可以用 n n n 位二进制数来存储每个 f ( x ) f(x) f(x)，其中第 i i i 位是 1 1 1 表示 x x x 能到 i i i，第 i i i 位是 0 0 0 表示 x x x 不能到 i i i。这样一来，对若干个集合求并就相当于对若干个二进制数进行按位或运算，每个 f ( x ) f(x) f(x) 中 1 1 1 的个数就代表了从 x x x 出发能够到达的节点的数量。

#include <bits/stdc++.h>

using namespace std;

const int N = 30010;

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

vector<int> L;
bitset<N> f[N];

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

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

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        L.push_back(t);

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        add(x, y), in[y]++;
    }

    topo_sort();

    for (int i = n - 1; ~i; i--) {  // 倒序遍历
        int j = L[i];
        f[j][j] = 1;  // j一定能到达自身
        for (int k = h[j]; ~k; k = ne[k])
            f[j] |= f[e[k]];  // 按照公式计算出f[j]的值
    }

    for (int i = 1; i <= n; i++) cout << f[i].count() << "\n";

    return 0;
}

3.5 Directing Edges

🔗 原题链接：CF 1385E

本题说白了就是给图中的所有无向边指定方向，使得最终得到的图是一个DAG。

我们可以先考虑仅由有向边构成的子图，如果这个子图都不是DAG，那么后续无论怎样为无向边指定方向（相当于添加有向边）都不可能构成DAG，此时应当输出 NO。如果这个子图是DAG，那么我们一定可以通过指定无向边的方向来构造出新的DAG。

具体来说，我们先对有向边构成的子图进行拓扑排序，于是可以得到一个拓扑序列。对于每一个无向边 ( a , b ) (a,b) (a,b)，若 a a a 在拓扑序列中的下标小于 b b b 在拓扑序列中的下标，则添加有向边 a → b a\to b a→b，否则添加有向边 b → a b\to a b→a，这样可以保证添加完有向边后得到的图仍然是DAG。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

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

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

void topo_sort(vector<int> &L) {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) q.push(i);

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        L.push_back(t);

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

void solve() {
    memset(h, -1, sizeof h);
    memset(in, 0, sizeof in);

    vector<int> L;
    vector<pair<int, int>> edges;

    cin >> n >> m;
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t) add(x, y), in[y]++;
        else edges.emplace_back(x, y);
    }

    topo_sort(L);

    if (L.size() != n) cout << "NO\n";
    else {
        cout << "YES\n";
        // 先输出有向图部分
        for (int i = 1; i <= n; i++)
            for (int j = h[i]; ~j; j = ne[j])
                cout << i << ' ' << e[j] << "\n";

        vector<int> pos(n + 1);  // 因为节点的编号是从1开始的，所以要多开一个
        for (int i = 0; i < n; i++) pos[L[i]] = i;
        // 再输出补全的部分
        for (auto [a, b]: edges) {
            if (pos[a] > pos[b]) swap(a, b);
            cout << a << ' ' << b << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

http://www.niftyadmin.cn/n/165115.html

相关文章

Spring BeanFactory源码中是如何创建对象

Spring BeanFactory源码中是如何创建对象

Spring BeanFactory 源码中是如何创建对象 目录 整体流程 上篇博客【 源码解析-Spring 如何从配置文件中读取文件】 中&#xff0c;我们聊到Spring中如何从配置中读取文件并转成BeanDefinitions 。今天我们继续来聊一下&#xff0c;Spring 如何基于 BeanDefinitions 加工成…
阅读更多...
【动态规划】最长上升子序列（单调队列、贪心优化）

【动态规划】最长上升子序列（单调队列、贪心优化）

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…
阅读更多...
原理底层计划---JVM

原理底层计划---JVM

二、JVM对空间大小怎么配置&#xff1f;各区域怎么划&#xff1f; 新生代&#xff1a;短时间生成&#xff0c;可以马上回收 老生代&#xff1a;少部分对象会存在很久&#xff0c;回收策略应不同 三、JVM哪些内存区域会发生内存溢出&#xff08;程序计数器不会&#xff09; …
阅读更多...
async与await异步编程

async与await异步编程

ECMA2017中新加入了两个关键字async与await 简单来说它们是基于promise之上的的语法糖&#xff0c;可以让异步操作更加地简单明了 首先我们需要用async关键字&#xff0c;将函数标记为异步函数 async function f() {} f()异步函数就是指&#xff1a;返回值为promise对象的函…
阅读更多...
万字长文带你初步理解计算机网络

万字长文带你初步理解计算机网络

目录 1.网络发展 2.认识 "协议" 和 标准 3.网络协议初识 4.OSI七层模型 5.TCP/IP 6.网络传输基本流程 首先&#xff0c;说到网络你的第一印象是什么&#xff1f; 站在普通人角度肯定就是我可以通过网络做各种事情&#xff0c;刷抖音看B站打王者还有今天在这里…
阅读更多...
Java进阶1 常用API

Java进阶1 常用API

API● 导图一、Object类二、Objects类三、 包装类3.1 包装类和基本数据的转换3.2 包装类型和String类型的相互转换3.3 包装类方法四、String类4.1 StringBuilder类4.2 StringJoiner类五、Arrays类六、Math类七、System类八、Runtime类九、BigDecimal类十、Date类十一、SimpleDa…
阅读更多...
（待完善）2023-selenium 实现知乎自动登录（第三方登录+需要扫二维码/使用cookie自动登录）+指定用户的信息相关搜集（2023.3）

（待完善）2023-selenium 实现知乎自动登录（第三方登录+需要扫二维码/使用cookie自动登录）+指定用户的信息相关搜集（2023.3）

目录一级目录二级目录三级目录零、写在前面一、自动登录&#xff1a;数据采集前&#xff0c;个人账号应通过程序自动登录&#xff0c;若遇到验证码可在程序中手动输入并继续登录二、指定用户基本属性信息采集三、社交关系信息四、动态信息&#xff08;一&#xff09;本文在多线…
阅读更多...
OpenCv + Qt5.12.2 文字识别

OpenCv + Qt5.12.2 文字识别

OpenCv Qt5.12.2 文字检测与文本识别 前言 ​ 好久没有进行一些相关的更新的了&#xff0c;去年一共更新了四篇&#xff0c;最近一直在做音视频相关的直播服务&#xff0c;又是重新学习积攒经验的一个过程。去年疫情也比较严重&#xff0c;等到解封&#xff0c;又一直很忙&a…
阅读更多...
最新文章

Copyright @ 2022~2023