前置芝士
概念
拓扑排序（Topological Sorting）是对有向无环图（DAG，Directed Acyclic Graph）的极点进行排序的一种算法。它将图中的全部极点排成一个线性序列，使得对于图中的任意一条有向边 (u, v)，极点 u 在序列中都出如今极点 v 之前。也就是说，拓扑排序的结果反映了图中极点之间的先后依靠关系。
需要留意的是，只有有向无环图才有拓扑排序，因为如果图中存在环，就无法满足先后顺序的要求。
算法流程
Kahn 算法（基于入度的算法）
-1统计入度：遍历图中的全部边，统计每个极点的入度（即指向该极点的边的数量）。
-2初始化队列：将全部入度为 0 的极点加入一个队列中。
-3拓扑排序过程：
-从队列中取出一个极点，并将其加入拓扑排序的结果序列中。
-对于该极点的全部毗邻极点，将它们的入度减 1。
-如果某个毗邻极点的入度变为 0，则将其加入队列。
-4检查结果：重复步调 3，直到队列为空。如果终极拓扑排序结果序列中的极点数量等于图中的极点数量，则说明图是有向无环图，得到的序列就是拓扑排序结果；否则，图中存在环，不存在拓扑排序。
具体的 C++ 算法
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 拓扑排序函数
vector<int> topologicalSort(int n, vector<vector<int>>& graph) {
// 存储每个极点的入度
vector<int> inDegree(n, 0);
// 存储拓扑排序的结果
vector<int> result;
// 队列用于存储入度为 0 的极点
queue<int> q;
// 统计每个极点的入度
for (int i = 0; i < n; ++i) {
for (int neighbor : graph) {
++inDegree[neighbor];
}
}
// 将全部入度为 0 的极点加入队列
for (int i = 0; i < n; ++i) {
if (inDegree == 0) {
q.push(i);
}
}
// 拓扑排序过程
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
// 遍历该极点的全部毗邻极点
for (int v : graph) {
--inDegree[v];
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// 如果拓扑排序结果的长度不等于极点数量，说明图中存在环
if (result.size() != n) {
return {}; // 返回空向量表示不存在拓扑排序
}
return result;
}
int main() {
int n = 6; // 极点数量
vector<vector<int>> graph(n);
// 添加有向边
graph[5].push_back(2);
graph[5].push_back(0);
graph[4].push_back(0);
graph[4].push_back(1);
graph[2].push_back(3);
graph[3].push_back(1);
vector<int> result = topologicalSort(n, graph);
if (result.empty()) {
cout << "图中存在环，不存在拓扑排序。" << endl;
} else {
cout << "拓扑排序结果：";
for (int vertex : result) {
cout << vertex << " ";
}
cout << endl;
}
return 0;
}
应用场景
任务调度：在项目管理中，任务之间可能存在先后依靠关系。可以将任务看作图的极点，任务之间的依靠关系看作有向边，通过拓扑排序可以确定任务的实行顺序，确保在实行某个任务之前，其全部前置任务都已经完成。
课程安排：在学校的课程体系中，某些课程可能需要先修其他课程。可以将课程看作极点，先修关系看作有向边，利用拓扑排序可以得到一个公道的课程学习顺序。
编译顺序：在软件开发中，源文件之间可能存在依靠关系。通过拓扑排序可以确定源文件的编译顺序，确保在编译某个文件之前，其全部依靠的文件都已经编译完成。
数据流分析：在计算机科学中，数据流图可以表示数据在系统中的流动和处理惩罚过程。拓扑排序可以用于确定数据处理惩罚的顺序，确保数据在被处理惩罚之前已经被正确生成。
练习题：
家谱图：
标准的板子题：
代码：
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,vector<int>>e;
const int N=110;
queue <int> Q;
int in[N];
int n;
void toposort() {
for(int i = 1; i <= n; i++) {
if(in == 0) {
printf("%d ", i);
Q.push(i);
}
}
while(Q.size()) {
int u = Q.front(); Q.pop();
for(int v:e) {
in[v]--;
if(in[v] == 0) {
printf("%d ", v);
Q.push(v);
}
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int tmp=0;
while(cin>>tmp,tmp!=0){
e.push_back(tmp);
in[tmp]++;
}
}
toposort();
}
奖金
分析：
差分约束的简化版，这里利用拓普排序，如果u->v,那么f[v]=max(f[v],f+1);
为什么是max？因为还有其他的u1连接到了v,万一u1的值更大，那么v就要满足>u1
所以要求的是满足一系列v>u,u1,u2....的v的最小值
至于如果把100搞定，当然可以直接把初值设置为100大概答案末了加100就好了
同时归纳下：
如果边权无限定，只有利用差分约束了
如果边权非负，那就可以利用tarjan算法
如果边权为正数，就可以利用拓扑排序来做了！
代码
可达性统计:
分析：
求拓扑序，然后倒序求出f,这里的f表示i之后可达的点的聚集
f=所以i的子节点能到的点的并集，这里的聚集我们用string来模仿01001的二进制串来表示
代码：
#include<bits/stdc++.h>
using namespace std;
// 定义常量 N 作为最大极点数
const int N = 30010;
// n 表示图的极点数量，m 表示图的边数量
int n, m;
// in 数组用于记载每个极点的入度，入度即指向该极点的边的数量
int in[N];
// q 数组作为队列利用，用于拓扑排序过程中存储入度为 0 的极点
int q[N];
// h 是队列的头指针，初始化为 0；t 是队列的尾指针，初始化为 -1
int h = 0, t = -1;
// f 数组是一个 bitset 数组，f 表示从极点 i 出发能够到达的全部极点的聚集// bitset 是一种高效存储二进制位的数据结构，这里用它可以方便地进行位运算
bitset<N> f[N];
// e 是一个无序映射，用于存储图的毗邻表// e 存储的是从极点 u 出发的全部边指向的极点
unordered_map<int, vector<int>> e;
// 拓扑排序函数，用于对有向图进行拓扑排序
bool toposort() {
// 遍历全部极点，将入度为 0 的极点加入队列
for (int i = 1; i <= n; i++) {
if (!in) {
// 入度为 0 的极点入队，尾指针后移
q[++t] = i;
}
}
// 当队列不为空时，持续进行处理惩罚
while (h <= t) {
// 取出队头元素
int u = q[h++];
// 遍历从极点 u 出发的全部边指向的极点
for (int v : e) {
// 将极点 v 的入度减 1，表示移除从 u 到 v 的边
--in[v];
// 如果极点 v 的入度变为 0，将其加入队列
if (!in[v]) {
q[++t] = v;
}
}
}
// 这里原代码直接返回 1，存在问题，正确应该判断是否拓扑排序乐成
// 若拓扑排序乐成，队列中应该存储了全部极点，即 t == n - 1
return t == n - 1;
}
int main() {
// 读取图的极点数量 n 和边的数量 m
scanf("%d%d", &n, &m);
// 循环读取每条边的信息
for (int i = 0; i < m; i++) {
int u, v;
// 读取边的起点 u 和终点 v
scanf("%d%d", &u, &v);
// 将终点 v 添加到起点 u 的毗邻表中
e.push_back(v);
// 终点 v 的入度加 1
in[v]++;
}
// 调用拓扑排序函数
if (!toposort()) {
// 如果拓扑排序失败，说明图中存在环，输出错误信息并退出程序
cerr << "图中存在环，无法进行可达性统计。" << endl;
return 1;
}
// 按照拓扑排序结果的逆序遍历极点
for (int i = n - 1; i >= 0; i--) {
// 取出当前处理惩罚的极点
int u = q;
// 极点 u 能到达自身，将 f 的第 u 位设为 1
f = 1;
// 遍历从极点 u 出发的全部边指向的极点
for (int v : e) {
// 通过位运算将 f[v] 能到达的极点合并到 f 中
f |= f[v];
}
}
// 遍历全部极点，输出每个极点能到达的极点数量
for (int i = 1; i <= n; i++) {
// count() 方法返回 bitset 中 1 的个数，即能到达的极点数量
cout << f.count() << endl;
}
return 0;
}
车站分级：
分析
这道题可以通过建立有向图并进行拓扑排序来求解火车站最少的级别数，以下是具体思绪：
建立有向图思绪
极点含义：将每个火车站看作图中的一个极点，编号为 1 到 n ，对应图中的 n 个极点。
边的构建：对于每一趟车次，设其停靠站为 si1,si2,⋯,sisi（按编号从小到大分列）。对于这趟车次的任意两个停靠站 sij 和 sik（j<k），在图中添加有向边 (sij,sik)。这是因为根据题目条件，如果一趟车次停靠了火车站 x，则始发站、终点站之间全部级别大于等于火车站 x 的都必须停靠，添加边表示了这种级别上的 “约束” 关系。更普通地理解，就是停靠靠前的车站可以 “指向” 停靠靠后的车站，意味着靠前车站的级别小于等于靠后车站的级别。
边的隐含意义：有向边 (u,v) 表示火车站 u 的级别小于等于火车站 v 的级别。通过这样构建有向图，就将车次运行情况转化为了图中极点之间的关系。
拓扑排序思绪
入度统计：在构建好有向图后，统计每个极点（即每个火车站）的入度，入度表示有多少条边指向该极点。
初始处理惩罚：把全部入度为 0 的极点（即没有其他极点的级别小于它的火车站）加入队列。这些极点可以看作是最低级别的候选者。
拓扑排序过程：
从队列中取出一个极点，这个极点代表的火车站可以被分别为一个级别。
对于该极点的全部毗邻极点（即由该极点出发的边指向的极点），将它们的入度减 1。这是因为已经处理惩罚了当前极点，与它相干的 “约束” 减少了。
如果某个毗邻极点的入度变为 0，则将其加入队列。这表示在处理惩罚完当前级别后，这个极点所代表的火车站也可以被确定为一个新的级别（在当前已处理惩罚的级别基础上）。
结果确定：重复上述步调，直到队列为空。每一轮从队列中取出极点并处理惩罚的过程，相当于确定了一个新的级别。终极统计处理惩罚的轮数，这个轮数就是 n 个火车站最少分别的级别数 。因为拓扑排序的特性保证了在处理惩罚过程中，先处理惩罚的极点级别不高于后处理惩罚的极点级别，通过这种方式能得到满足车次运行要求的最少级别分别。
建立边的及技巧
9 2
4 1 3 5 6
这里的1->3->5->6,可以如下优化
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=2010;
unordered_map<int,vector<pair<int,int>>>e;
int n,m;
int in[N];
bool st[N];
int q[N];
int dis[N]={0};
int h=0,t=-1;
void toposort(){
for(int i=1;i<=n;i++)
if(!in)q[++t]=i;
while(h<=t){
int u=q[h++];
for(auto ww:e){
int v=ww.first;
if(--in[v]==0){
q[++t]=v;
}
}
}
}int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
memset(st,0,sizeof st);
int cnt;
cin>>cnt;
int start=n,end=1;
for(int j=0;j<cnt;j++){
int stp;
scanf("%d",&stp);
start=min(start,stp);
end=max(end,stp);
st[stp]=1;
}
int v=i+n;
for(int i=start;i<=end;i++){
if(st){
e.push_back({v,0});
in[v]++;
}
else {
e[v].push_back({i,1});
in++;
}
}
}
toposort();
for(int i=1;i<=n;i++)dis=1;
for(int i=0;i<n+m;i++){
int u=q;
for(auto ww:e){
int v=ww.first,w=ww.second;
dis[v]=max(dis[v],dis+w);
}
}
int res=0;
for(int i=1;i<=n;i++)res=max(res,dis);
cout<<res;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
