目录
拓扑排序
定义
拓扑排序（Topological Sort）是对有向无环图（Directed Acyclic Graph，简称DAG）的一种排序方式。在一个有向无环图中，拓扑排序的结果是一个线性的顶点序列，其中对于图中的每一条有向边 (u, v)，顶点 u 在序列中都会出现在顶点 v 的前面。如果一个图有多个拓扑排序，那么它不是一个唯一的排序，但所有合法的拓扑排序都符合上述规则。
运用情况
- 任务调度：例如，项目管理中的依赖关系，先决条件的课程计划，构建系统中的依赖项解析。
- 编译器优化：在编译过程中确定指令的最优执行顺序。
- 数据流分析：在程序分析中，为了确定变量的使用和定义顺序。
- 资源分配：在资源有限的情况下，确定资源的使用顺序。
注意事项
- 图的合法性：图必须是一个有向无环图（DAG）。如果图中含有环，则拓扑排序不可能成功。
- 入度的概念：入度是指指向一个顶点的边的数量。拓扑排序的算法通常会从入度为0的顶点开始。
- 排序非唯一性：对于同一个DAG，可能存在多个合法的拓扑排序序列。
- 算法效率：拓扑排序的时间复杂度通常是 O(V+E)，其中 V 是顶点数，E 是边数。
解题思路
- 构建图：使用邻接表或邻接矩阵表示图的数据结构。
- 计算入度：对于每个顶点，计算其入度（即有多少条边指向它）。
- 选择起始点：从入度为0的顶点开始，因为它们没有任何前置条件。
- 递归或迭代：将入度为0的顶点加入结果序列，然后将其从图中移除（或标记为已处理），并减少与之相连的其他顶点的入度。重复此过程直到图中没有剩余的顶点或无法找到入度为0的顶点。
- 检查结果：如果所有顶点都被处理且结果序列的长度等于顶点总数，则排序成功。如果有顶点未被处理或结果序列长度小于顶点总数，则图中存在环，排序失败。
一个常见的算法实现是使用队列或栈进行迭代处理，每次从队列或栈中取出入度为0的顶点，更新其邻接顶点的入度，并重复这一过程，直到队列或栈为空。
AcWing 164. 可达性统计
题目描述
运行代码
#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;
const int N = 30010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];
bitset<N> f[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void topsort()
{
bool inQueue[N] = {false}; // 标记是否已经入队
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
{
if (!d[i])
{
q[++tt] = i;
inQueue[i] = true; // 标记入队
}
}
while (hh <= tt)
{
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i])
{
if (--d[e[i]] == 0 &&!inQueue[e[i]]) // 未入队才入队
{
q[++tt] = e[i];
inQueue[e[i]] = true; // 标记入队
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
if (!(cin >> n >> m)) // 输入错误处理
{
cerr << "Invalid input. Please enter valid integers." << endl;
return 1;
}
while (m--)
{
int a, b;
if (!(cin >> a >> b)) // 输入错误处理
{
cerr << "Invalid input. Please enter valid integers for the edge." << endl;
return 1;
}
add(a, b);
d[b]++;
}
topsort();
for (int i = n - 1; i >= 0; i--)
{
int j = q[i];
f[j][j] = 1;
for (int k = h[j]; ~k; k = ne[k])
f[j] |= f[e[k]];
}
for (int i = 1; i <= n; i++)
cout << f[i].count() << endl;
return 0;
}代码思路
-
图的表示：使用邻接表存储图的结构，其中
h,e,ne分别表示头指针数组、边的目标节点和边的下一个节点。 -
入度计算：
d数组用来存储每个节点的入度（即有多少条边指向该节点）。 -
拓扑排序：
topsort函数实现了拓扑排序算法，首先将所有入度为0的节点入队，然后循环处理队列中的节点，当处理完一个节点后，将它的所有后继节点的入度减一，如果某个后继节点的入度变为0，则将它入队，直到队列为空。 -
可达性统计：在拓扑排序完成后，
f数组是一个位向量数组，用于存储从每个节点出发可以到达的所有节点。从最后一个节点开始向前回溯，对于每个节点j，初始化f[j][j] = 1表示自身可达，然后对于j的每一个后继节点k，将f[j]与f[k]进行按位或运算，从而合并所有后继节点的可达信息。 -
输出结果：最后，遍历
f数组，输出从每个节点出发可以到达的节点数。
改进思路
-
空间优化：使用位向量数组
f能够有效节省空间，相比于使用整型数组，位向量数组可以更紧凑地存储信息。 -
时间优化：拓扑排序的实现是高效的，但是遍历所有的边来更新可达性信息可能会相对耗时。确保数据结构和算法的正确性和效率至关重要。
-
输入验证：代码中包含了对输入的验证，确保了程序在遇到非法输入时能够给出错误提示并安全退出。
- 避免重复检查：在拓扑排序过程中，
inQueue数组用于避免节点被重复入队，这是必要的，因为它避免了不必要的队列操作。 - 简化可达性计算：在回溯阶段，可以尝试避免不必要的按位或运算，但这可能取决于具体的输入数据和图的特性，不一定总是可行。