7/20 拓扑/Tarjan
小组成员：吴予涵、郑荣、林育辰、许文博、刘天顺。
拓扑
导入
给定一张有向图，构造一个满足一下条件的节点序列：对于每条有向边 (u, v)，序列中 v 排在 u 之后（若序列存在，则图中不存在环）。
若 u 有边指向 v，则说 u 是 v 的前驱，v 是 u 的后继。
不允许任何一个点在当其前驱没有被放入序列时被放入序列。
设 d_x 为点 x 的入度，用队列储存入度为 0 的点（即没有前驱的点）。
每次从队列中取出一个点，并把该点连边指向的所有点入度减 1，若连向的点入度为 0 则入队。所有点的出队顺序即为一组合法拓扑序列。
有向无环图（DAG）能进行拓扑。
for {
统计所有点入度;
if (入度 == 0) {
q.push(i);
}
}
while (q.size()) {
int u = q.front();
q.pop(); // 出队顺序就是拓扑排序的结果
for (遍历 u 出发的所有边) {
in[v]--;
if (in[v] == 0) q.push(v);
}
}
变式
如果判断拓扑序的唯一性？ 队列的长度是否始终小于 2。
如何求出字典序最小的拓扑序？ 使用优先队列，在有多个可选节点时选择最小的入队。
给定一张 DAG，边有边权，求边权和最大的路径？ 设 dp_i 为以 i 为结尾的最长路的长度，dp_i = \max(dp_{i \text{ 的前驱}} + w_{val})。
while (q.size()) {
取出队首;
for (遍历从 u 出发的边) {
dp[v] = max(dp[v], dp[u] + wi);
}
}
给定一张 DAG，点有点权，求点权和最大的路径？
给定一张 DAG，求图中的路径条数？ 设 dp_i 为到达 i 的路径数。dp_i = \sum dp_{i \text{ 的前驱}}。
加法原理：到达一个状态的方案数等于到达当前状态的所有状态到达方案之和。
例题
起飞序列
考虑反向建图。
对于第一问，从后往前安排，每次取一个符合要求的航班起飞。
对于第二问，对除当前飞机以外的飞机进行拓扑，直到队列为空，则此时的位置为当前飞机的正确顺序。
Tarjan
连通分量（无向图中的连通块）：对于其中的任意两个点 i, j，i 到 j 和 j 到 i 都存在至少一条路径。
强连通分量（有向图中的 “双向可达连通块”）：对于其中的任意两个点 i, j，i 到 j 和 j 到 i 都存在至少一条路径。
一般可以用 Tarjan 求有向图的强连通分量及其相关信息。
从任意一点出发搜索遍历一张有向图，每个节点只访问一次，只保留所有搜索递归回溯的边，可以得到一棵生成树。
环是最简单的强连通分量。Tarjan 算法的基本思想是找出所有能跟它构成环的点。
x 可达 y 当且仅当以下两种情况：
- 从 x 出发有一条指向 y 的返祖边。
- 从 x 出发有一条横叉边指向 z，而 z 有到达 y 的路径。
对于每个未访问过的节点，遍历其搜索树，同时用栈存储访问到的点。
定义：dfn_u 表示 u 的 dfs 序，low_u 表示 u 或 u 的子树节点，只经过最多一条返祖边能够追溯到的最早的 dfn。
low_u = \min(dfn_u, low_v, dfn_v)，low_v 中 v 在 n 的子树里，dfn_v 中 (u, v) 为返祖边或横向边。
void tarjan(int x) {
dfn[x] = low[x] = ++top;
vis[x] = 1;
q.push(x); // stack<int> q;
for (int i = head[x]; i != -1; i = a[i].next) {
if (!dfn[a[i].to]) {
tarjan(a[i].to);
low[x] = min(low[x], low[a[i].to]);
} else if (vis[a[i].to]) {
low[x] = min(dfn[a[i].to], low[x]);
}
}
}
结论：当 dfn_u = low_u 时，以 u 为根的未出栈子树节点是一个强连通分量，将它们依次弹出记录即可。
证明：所有未出栈子树节点都在此强连通分量内，所有除此之外的节点都不可能在此强连通分量内。
if (dfn[x] == low[x]) {
cnt++;
while (q.top() != x) {
vis[q.top()] = 0;
b[q.top()] = cnt;
q.pop();
}
vis[x] = 0;
b[x] = cnt;
q.pop();
}
求出强连通分量的作用？
将每个强连通分量缩成一个点，新图中两个点之间有边当且仅当原图中对应两强连通分量的点之间有边。
这样得到的新图一定是 DAG。
对于无向图中一点 x，若删掉 x 和与 x 相连的边后新图不连通，则 x 为图的割点。若图中不存在割点，则该图为点双连通图。
若点 x 是树根，且存在多个子节点则 x 是割点；若点 x 不是树根，且存在一个子节点 y 满足 dfn_x \le low_y 则 x 是割点。
例题
间谍
任何一个强连通分量中 “收买” 最便宜的点。使用 Tarjan 进行缩点，点权设为原图中的最小值。
检查所有入度为 0 的点是否都能被收买，将其花费求和即可。
P3387 模板缩点
记 dp_i 为走到 i 的最大的权值和，dp_i = \max(dp_\text{前驱}, val_i)。