1.引入：身边的拓扑排序
做番茄炒蛋：
-
先洗番茄，再切番茄
-
先打蛋，再搅拌蛋液
-
切番茄和搅拌蛋液可以同时准备
-
都准备好之后，才能下锅炒
拓扑排序就能给我们提供一种合理的顺序，如：
洗番茄 → 切番茄 → 打蛋 → 搅拌蛋液 → 下锅翻炒
2.什么是拓扑排序
-
作用:对有向无环图的所有顶点进行排序
-
排序标准：假如\(A\)节点指向\(B\)节点，那么\(A\)节点一定排在\(B\)节点之前
例子：
通过简单的推理，我们可以发现，这个有向无环图中的一种合理顺序为：
2 → 4 → 5 → 3 → 1
3.拓扑排序的实现方法
对于上面的例子，我们可以检测每个节点的入度（即有多少个节点指向此节点）：
-
节点1的入度为： 2
-
节点2的入度为： 0
-
节点3的入度为： 2
-
节点4的入度为： 1
-
节点5的入度为： 2
第一步：
在图中找出入度为0的节点，放入q队列：
第二步：
将队列的第一个数放入答案队列的末尾，并将此节点指向的所有节点入度减一，并将入度为0的节点加入队列（不重复入队）：
第三步：
重复步骤2，直到队列q为空：
↓
↓
↓
此时队列q为空，答案为队列ans
3.代码实现
#include<bits/stdc++.h>//万能头文件
using namespace std;
vector<int>e[105];//存储有向图中边的关系，e[i]中存储第i个节点指向的所有节点
int n;
queue<int>q;//临时队列，存储入度为0的节点
int d[105];//存储入度
int vis[105];//是否访问过
int main() {cin>>n;//输入边数/节点数for(int i=1;i<=n;i++) {while(1) { int a;cin>>a;e[i].push_back(a);//存储有向边if(a==0) {break;}d[a]++;//记录入度}}for(int i=1;i<=n;i++) {if(d[i]==0) {q.push(i);//将入度为0的加入队列vis[i]=1;//标记以访问}}while(!q.empty()) {//队列非空int x=q.front();//取出队列第一项q.pop();cout<<x<<" ";//输出答案for(int i:e[x]) {//枚举节点x指向的所有节点if(vis[i]) continue;//确保节点未被访问过d[i]--;//将入度减少1if(d[i]==0) {//入度为0vis[i]=1;//标记已访问q.push(i);//加入队列}}}return 0;
}
4.例题讲解
P4017 最大食物链计数
题目背景
你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。
题目描述
给你一个食物网，你要求出这个食物网中最大食物链的数量。
（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 \(1\) 秒的时间。
由于这个结果可能过大，你只需要输出总数模上 \(80112002\) 的结果。
输入格式
第一行，两个正整数 \(n\)、\(m\)，表示生物种类 \(n\) 和吃与被吃的关系数 \(m\)。
接下来 \(m\) 行，每行两个正整数，表示被吃的生物 A 和吃 A 的生物 B。
输出格式
一行一个整数，为最大食物链数量模上 \(80112002\) 的结果。
输入输出样例 #1
输入 #1
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
输出 #1
5
说明/提示
各测试点满足以下约定：
| 测试点编号 | \(n\) | \(m\) |
|---|---|---|
| \(1,2\) | \(\le 40\) | \(\le 400\) |
| \(3,4\) | \(\le 100\) | \(\le 2\times 10^3\) |
| \(5,6\) | \(\le 10^3\) | \(\le 6\times 10^4\) |
| \(7,8\) | \(\le 2\times 10^3\) | \(\le 2\times 10^5\) |
| \(9,10\) | \(\le 5\times 10^3\) | \(\le 5\times 10^5\) |
对于 \(100\%\) 的数据，\(1 \le n \le 5\times 10^3,1\le m \le 5\times 10^5\)
【补充说明】
数据中不会出现环，满足生物学的要求。（感谢 @AKEE）
4.1主要思路
拓扑排序+dp
-
状态定义：\(dp[i]\) 表示到达节点\(i\)的路径数
-
初始化：将所有入度为0的点标记为1
-
状态转移方程：\(dp[i]=所有指向i节点的路径数量总和\)
4.2代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=80112002;
vector<ll>e[5005];//存储有向边
ll n,m;//n为节点数，m为边数
queue<ll>q;//临时存储入度为0的节点
ll d[5005],s[5005],c[5005];//d存储入度，s存储答案，c存储出度（即此节点指向多少个节点）
int main() {cin>>n>>m;//输入for(ll i=1;i<=m;i++) {ll a,b;cin>>a>>b;//输入e[a].push_back(b);//节点a指向节点bd[b]++;//更新入度c[a]++;//更新初读}for(ll i=1;i<=n;i++) {if(d[i]==0) {//检测是否入度为0q.push(i);//存入队列s[i]=1;//标记路径数量为1}}ll ans=0;//答案，初始化为0while(!q.empty()) {//队列不为空ll x=q.front();//获取队首元素q.pop();for(ll i:e[x]) {//遍历节点x指向的所有节点d[i]--;//入度减1s[i]+=s[x];//更新到达节点i的路径数量s[i]%=N;//取modif(d[i]==0) {q.push(i);//加入队列}}}for(int i=1;i<=n;i++) {if(c[i]==0) {//判断初读ans+=s[i];//答案为出度为0的所有元素路径数量总和ans%=N;}}cout<<ans;//输出答案return 0;
}
5.推荐练习题目
-
洛谷B3644 【模板】拓扑排序 / 家谱树
-
洛谷P4017 最大食物链计数
-
洛谷P3074 [USACO13FEB] Milk Scheduling S
-
洛谷P1807 最长路
-
洛谷P1137 旅行计划
-
洛谷P1113 [USACO02FEB] 杂务
-
洛谷P3183 [HAOI2016] 食物链