代码编织梦想

一、什么是拓扑排序?

拓扑排序是一种有向无环图(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 的有向边,于是可以得到:

9a4ff784fbb449399a0042713c4d9854.png

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

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

此外还可以证明,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}yN(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 ab,否则添加有向边 b → a b\to a ba,这样可以保证添加完有向边后得到的图仍然是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;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/raelum/article/details/129650604

面试遇到了算法题?看这篇就够啦。_varyall的博客-爱代码爱编程

原文地址:github.com/kdn251/interviews译文出自:掘金翻译计划译者:王下邀月熊校对者:PhxNirvana、根号三这个 链接 用来查看本翻译与英文版是否有差别(如果你没有看到 README.md 发生变化,那就意味着这份翻译文档是最新的)。 Interviews 软件工程技术面试个人指南。 Maintaine

解析微服务架构组件,看这一篇文章就够_csdn业界要闻的博客-爱代码爱编程

1. 如何发布和引用服务 服务描述:服务调用首先解决的问题就是服务如何对外描述。 常用的服务描述方式包括 RESTful API、XML 配置以及 IDL 文件三种。 RESTful API 主要被用作 HTTP 或者 HTTPS 协议的接口定义,即使在非微服务架构体系下,也被广泛采用 优势:HTTP 协议本身

算法与数据结构?看这篇就够了_程序员的那些事_的博客-爱代码爱编程

程序 = 数据结构 + 算法              ——图灵奖得主,计算机科学家N.Wirth(沃斯) 作为程序员,我们做机器学习也好,做python开发也好,java开发也好。 有一种对所有程序员无一例外的刚需 —— 算法与数据结构 日常增删改查 + 粘贴复制 + 搜索引擎可以实现很多东西。 同样,这样也

数据结构与算法?看这篇就够了!_hadoop技术博文的博客-爱代码爱编程

程序 = 数据结构 + 算法              ——图灵奖得主,计算机科学家N.Wirth(沃斯) 作为程序员,我们做机器学习也好,做python开发也好,java开发也好。 有一种对所有程序员无一例外的刚需 —— 算法与数据结构 日常增删改查 + 粘贴复制 + 搜索引擎可以实现很多东西。 同样,这样也

数据结构与算法?看这篇就够了!!!-爱代码爱编程

程序 = 数据结构 + 算法              ——图灵奖得主,计算机科学家N.Wirth(沃斯) 作为程序员,我们做机器学习也好,做Python开发也好,Java开发也好。 有一种对所有程序员无一例外的刚需 —— 算法与数据结构 日常增删改查 + 粘贴复制 + 搜索引擎可以实现很多东西。 同样,这样也

-2017年秋招面试遇到了算法题?看这篇就够啦_weixin_30740295的博客-爱代码爱编程

Interviews 软件工程技术面试个人指南。 Maintainer - Kevin Naughton Jr. 目录 在线练习在线面试编程数据结构算法位运算算法复杂度分析视频教程面试书籍计算机科学与技术资讯 在线练习 LeetCodeVirtual JudgeCareerCupHackerRankCodeFigh

数据结构与算法?看这篇就够了!-爱代码爱编程

数据结构与算法?看这篇就够了! 幂次学院 算法爱好者 昨天 程序 = 数据结构 + 算法                ——图灵奖得主,计算机科学家N.Wirth(沃斯)   幂次学院,“人工智能”公众号旗下教育品牌特推出数据结构与算法系统大课 133节讲解 + 133节刷题,一共266节课每节课一小时,共266小时   作为

大厂技术面试必问的算法,看这一篇就够了-爱代码爱编程

金三银四来了,各大厂动静不小,都在储备人才,绝对是程序员面试的黄金时间了,不少同学也在后台反馈面试中遇到的一些问题,所以今天想跟大家说说算法。   说起算法,那大厂面试是绝对必考的,可以说是一块大厂的敲门砖。毕竟掌握算法,代码水平一定差不了,还能更快的掌握新技术的核心要领。大厂技术更新更快,需要的就是能快速适应的人才。年薪几十万,是留给有准备的人

面试必问的算法,看这一篇就够了-爱代码爱编程

金三银四来了,各大厂动静不小,都在储备人才,绝对是程序员面试的黄金时间了,不少同学也在后台反馈面试中遇到的一些问题,所以今天想跟大家说说算法。   说起算法,那大厂面试是绝对必考的,可以说是一块大厂的敲门砖。毕竟掌握算法,代码水平一定差不了,还能更快的掌握新技术的核心要领。大厂技术更新更快,需要的就是能快速适应的人才。年薪几十万,是留给有准备的人

Redis这一篇就够了-爱代码爱编程

概述 什么是Redis Redis(Remote Dictionary Server) 是一个使用 C 语言编写的,开源的(BSD许 可)高性能非关系型(NoSQL)的键值对数据库。 Redis 可以存储键和五种不同类型的值之间的映射。键的类型只能为字符串,值 支持五种数据类型:字符串、列表、集合、散列表、有序集合。 与传统数据库不同的是 Red

想要彻底搞懂大厂是如何实现Redis高可用的?看这篇文章就够了-爱代码爱编程

高可用HA(High Availability)是分布式系统架构设计中必须考虑的因素之一,它通常是指,通过设计减少系统不能提供服务的时间。 假设系统一直能够提供服务,我们说系统的可用性是100%。如果系统每运行100个时间单位,会有1个时间单位无法提供服务,我们说系统的可用性是99%。很多公司的高可用目标是4个9,也就是99.99%,这就意味着,系统的年

排序算法看这一篇就够了-爱代码爱编程

1,排序算法的介绍 排序的分类: 内部排序: 指将需要处理的所有数据都加载到**内部存储器(内存)**中进行排序。 外部排序法: 数据量过大,无法全部加载到内存中,需要借助**外部存储(文件等)**进行排序。 常见的排序算法分类(见下图): 2,算法的时间复杂度 2.1,度量一个程序(算法)执行时间的两种方法 事后统计的方法 这种方

Java面试?看这一篇就够了-爱代码爱编程

注:以下内容仅为自己学习时所做笔记 Java面试 Java面向对象有哪些特征,如何应用HashMap原理是什么,在jdk1.7和1.8中有什么区别ArrayList和LinkedList有什么区别高并发中的集合有哪些问题jdk1.8的新特性有哪些一、接口的默认方法二、Lambda 表达式三、函数式接口四、方法与构造函数引用五、Lambda 作用域六、

拓扑排序与深度优先遍历_woaitianbin的博客-爱代码爱编程

以力扣210题进行分析 题目简介实现代码下面是非正常思维 题目简介 下面首先给出题目的简单介绍,笔者有些懒,直接截图。 实现代码 下面给出我实现的代码,说来也惭愧,冷落了拓扑排序了,居然在实现

[牛客算法总结]:重建二叉树-爱代码爱编程

   标签: 二叉树、DFS、先序遍历、中序遍历、递归   题目: 给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中

数模笔记——论文写作-爱代码爱编程

论文写作 各模块写作要点 数学建模论文的重要性 数学建模论文的写作是数学建模中重要的一个环节。数学建模的论文是参赛队工作的全面总结,也是评委评价建模成绩的主要依据一篇好的论文应该逻辑清晰,在语言表述上清楚,数学符号标记

动态规划算法-爱代码爱编程

一、前言 动态规划是一种常用的算法,在算法领域十分重要,但对于新手来说,理解起来有一定的挑战性,这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用。 二、解析动态规划算法 1.特点 ①把原来的问题分解成了【要点相同】的子问题(这个要点可以和后面讲的状态联系起来理解) ②所有问题都只需要解决一次(解决一次就是只需要由后面所说

p2568 gcd(欧拉函数,二维平面思想)_输入一行一个整数x输出一行一个整数表示答案-爱代码爱编程

题目描述 给定正整数 n,求 1≤x,y≤n 且 gcd(x,y) 为素数的数对 (x,y) 有多少对。 输入格式 只有一行一个整数,代表n。 输出格式 一行一个整数表示答案。 输入输出样例 输入 #1复制 4 输出 #1复制 4 说明/提示 样例输入输出 1 解释 对于样例,满足条件的 (x,y)为 (2,2),(2,4),(3