拓扑排序（竞赛）

一、介绍

1、介绍

有时候做一些事情是有前置条件的，能正确把这些事情排序出来的算法就是拓扑排序。

拓扑排序解决的是有向无环图，但是可以也可以判环。

2、实现思路

步骤1：一开始入度为0的节点是没有前置条件的，全部入队。

步骤2：出队头，删边，有节点入度为0，入队。

步骤3：一直循环步骤2，直到队列为空，即没有节点入度为0。

此时两种情况：

（1）全部节点入队出队过，说明全部任务做完，符合要求.

（2）没有全部节点入队出队过，说明有环。

3、例题

B3644 【模板】拓扑排序 / 家谱树 - 洛谷

#include <bits/stdc++.h>
using namespace std;int n;
vector<int> rel[110];
int in[110];
int cnt = 0;// 拓扑排序：一开始把入度为0的节点加入队列，开始循环，每次队头出一个节点，删除关联边（对应终点入度--，如果减到0就入队），直到全部节点入队或没有入度为0的节点终止
// 如果终止后不是所有节点都入过队那就说明有环，即cnt != nint main()
{cin >> n;for(int i = 1; i <= n; i++){int x;while(cin >> x, x){rel[i].push_back(x);in[x]++;}}queue<int> q;for(int i = 1; i <= n; i++)if(in[i] == 0)q.push(i);cnt = q.size();while(q.size()){int x = q.front();cout << x << ' ';q.pop();for(auto num : rel[x]){in[num]--;if(in[num] == 0){q.push(num);cnt++;}}}return 0;
}

二、例题

拓扑排序重点是排出一个合法的顺序，所以题型多样，可以和动态规划相结合，可以看成普通动态规划是按从小到大或从大到小顺序更新 dp 表，而与拓扑排序结合后用的是拓扑排序的顺序更新 dp 表，初始化一般在步骤一完成。

1、摄像头

P2712 摄像头 - 洛谷

#include <bits/stdc++.h>
using namespace std;int n;
vector<int> rel[510];
int in[510];
int cnt = 0;
vector<int> she;int main()
{cin >> n;for(int i = 1; i <= n; i++){int x;cin >> x;she.push_back(x);int j;cin >> j;while(j--){cin >> x;in[x]++;}}queue<int> q;for(auto x : she)if(in[x] == 0)q.push(x);cnt = q.size();while(q.size()){int x = q.front();q.pop();for(auto num : rel[x]){in[num]--;if(in[num] == 0){q.push(num);cnt++;}}}if(cnt == n)cout << "YES";else cout << n - cnt;return 0;
}

2、最大食物链计数

P4017 最大食物链计数 - 洛谷

#include <bits/stdc++.h>
using namespace std;const int mod = 80112002;
int dp[5010];
vector<int> rel[5010]; // 被吃
int in[5010]; // 吃节点的入度
int n, m;
int ans = 0;
// dp[i]表示从最前面到i生物的全部路径数
int main()
{cin >> n >> m;while(m--){int x, y;cin >> x >> y;rel[y].push_back(x);in[x]++;}queue<int> q;for(int i = 1; i <= n; i++){if(in[i] == 0){q.push(i);dp[i] = 1;}}while(q.size()){int x = q.front();q.pop();for(auto num : rel[x]){in[num]--;if(in[num] == 0)q.push(num);dp[num] = (dp[num] + dp[x]) % mod;}}for(int i = 1; i <= n; i++){if(rel[i].size() == 0){ans = (ans + dp[i]) % mod;}}cout << ans;return 0;
}

3、杂务

P1113 杂务 - 洛谷

#include <bits/stdc++.h>
using namespace std;int n;
vector<int> rel[10010];
int t[10010];
int in[10010];
int dp[10010];// 由于每一层的任务不是同时开始的，所以前置任务的最早完成时间是当前任务的开始时间
// 动态规划+拓扑排序
// dp[i]表示i任务最早完成时间
// dp[i] = max(dp前置任务) + t[i];int main()
{cin >> n;for(int i = 1; i <= n; i++){int x;cin >> x;cin >> t[x];int j;while(cin >> j, j){rel[j].push_back(x);in[x]++;}}queue<int> q;int ans = 0;for(int i = 1; i <= n; i++){if(in[i] == 0){q.push(i);dp[i] = t[i];}}while(q.size()){int x = q.front();ans = max(ans, dp[x]);q.pop();for(auto num : rel[x]){in[num]--;dp[num] = max(dp[num], dp[x] + t[num]);ans = max(ans, dp[num]);if(in[num] == 0)q.push(num);}}cout << ans;return 0;
}