拓扑 & Tarjan
拓扑排序
运用条件：
- 1.有向无环图
- 2.需要求拓扑序
例子：给定一张有向图， 构造一个满足以下条件的节点序列：对于图每条有向边 (u, v) ,序列中 v 排在 u 之后。
Solution:
设 d[x] 为点 x 的入度， 用队列维护入度为0的点， 每次从队列中取出一个点， 并把该点连边指向的所有点入度-1， 若连向的点入度为0则入队， 所有点的出队顺序即为一组合法序列。
对于一个图，如何判断其拓扑序是否唯一？
在跑拓扑排序的时候判断队列大小是否始终为1，若队列大小不为1，则此时拥有多种选择，故拓扑序不唯一。
来看下一个问题：如何求出字典序最小的拓扑序列？
讲队列改为优先队列，在有多个可选节点时将最小的点入队。
eg1. 给定一张 DAG (有向无环图)，边有边权， 求一条边权和最大的路径？
Solution:
dp[i] 为以 i 为结尾的最长路长度， dp[i] = \max(dp[前驱] + w_k, dp[i]) 。
while(非空)
{
取出队首;
for(遍历从u出发的边)
{
dp[v] = max(dp[v], dp[u] + w[i]);
in[v]--;
if(in[v] == 0) 入队
}
}
eg3.给定一张 DAG (有向无环图)， 求图中的路径条数？
根据加法原理： dp[i] 表示到 i 的路径条数， dp[v] += $dp[u]$。
eg4. 航空管制
经过思考，贪心假了，可能导致后续航班无法符合要求，因为拓扑排序时无法预测之后的航班安排是否有调整空间。
Solution ：倒着做！反向建图，从后向前计算拓扑序列，第一问从后向前安排， 每次取一个符合要求的航班起飞，第二问对除当前飞机以外的部分跑拓扑，直到队列为空则此时的位置即为当前飞机的答案。
Tarjan
前置知识: 连通分量， 强连通分量， 树上边。
连通分量：无向图中的连通块， 即对于连通分量中的任意两个点$i, j$,
i 到 j 和 j 到 i 都存在至少一条路径。
强连通分量： 有向图中的 “双向可达连通块”。
即对于强连通分量中的任意两个点$i, j$， i 到 j 和 j 到 $i$都存在至少一套路径。
树上边：
- 树边：搜索书上的边
- 前向边：从祖先指向后代的边
- 返祖边：从后代指向祖先的边
- 横向边：上述以外的边
一个结论或者说性质：$dfs$搜索一张无向图， 搜索树上一定不含
正题：
介绍：一般可以用tarjan算法求有向图的强连通分量（ SCC ）及其相关信息。从任意一点出发搜索遍历一张图（的一部分）， 每个节点仅防问一次， 只保留所有搜索递归回溯的边， 可以得到一颗生成树。
若要使$x$ 可以指向 $y$， 则满足以下条件之一
- 1.从 x 出发有一条指向 y 的返祖边
- 2.从 x 出发， 有一条横叉边指向 z ,而 z 有到达 y 的路径。
而Tarjan的做法是对每个未访问过的节点，遍历其搜索树，同时用栈存储访问到的点。
定义：
- dfn[u] 为节点 u 的 dfs 序
- low[u] 为 u 或 u 的子树节点，只经过最多一条返祖边， 能够追溯到的最早的 dfn.
low[u] = \min{
- dfn[u],
- low[v], v 在 u 的子树里
- dfn[v], (u, v) 为返祖边 （或横向边）
}
结论：当 dfn[u] == low[u] 时， 以 u 为根的未出栈子树节点是一个强连通分量，将他们依次弹出并记录即可。
代码实现
for(int i = 1;i <= n;i++)
if(!dfn[i])
tarjan(i);
void tarjan(int x){
dfn[x] = low[x] = ++top;
vis[x] = 1;
stk.push(x)
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]);
}
if(dfn[x] == low[x]){
cnt++;//cnt表示SCC数量
while(stk.top() != x)
{
vis[q.top()] = 0;
b[stk.top()] = cnt;
stk.pop();
}
vis[x] = 0;
b[x] = cnt;
stk.pop();
}
求出强连通分量能干啥？
缩点：将每个强连通分量缩成一个点， 新图中两个点之间有边 当且仅当 原图中对应的两强连通分量之间有边。就可以把有向无环图变为无向图， 而 $DAG$（有向无环图）具有许多优良的性质。
Solution:
显然一个强连通分量中只需要收买最便宜的点， tarjan缩点， 点权设为原图中点的最小值 ，然后计算新图中所有入度为0的点是否都能被收买， 将其花费求和即可。
eg7. 最大半连通子图
任意一个强连通分量中的点两两双向可达， 故一个强连通分量都在同一个半连通子图中或都不在。
割点
对于无向图中一点 x ，若删掉 x 和与 x 相连的边后新图不连通 则称 x 为图的割点。 若图中不存在割点， 则该图为点双连通图。
如何判断割点？
若点 x 是树根， 且存在多个子节点， 则 x 是割点
若点 x 不是树根， 且存在一个子节点 y ， 满足 $dfn \le low[y]$， 则 x 是割点。
割边
对于无向图中一条边， 若删掉该边后新图不连通， 则该边为图的割边， 也称作桥， 若图中不存在割边， 则该图为边双连通图
如何判断割边？
若 x 存在一个子节点 $y$， 满足 dfn[x] < low[y] 则 (x, y) 的连边是割边.
小组成员:邵品渊， 邵品砚， 蒋佳成， 顾天泽， 马天翔， 陈继禹