Tarjan 和一些连通性

Tarjan

图上可能有些环，Tarjan 就是处理这些环的方法。

Tarjan 维护两个值，dfs 序 $\mathrm{dfn}$ 和回溯值 $\mathrm{low}$ 。其中，对于搜索树上的一个节点 $u$ ，其回溯值为，

$$\min\left(\min_{v\in\mathrm{son}(u)}\{\mathrm{low}_v\},\min_{\exists(v,w)\in E\wedge v\notin\mathrm{son}(u)\wedge w\in\mathrm{son}(u)}\{\mathrm{dfn}_v\}\right) $$

可见回溯值就是处理环的重要方法。

void Tarjan (int u) {
	dfn[u] = low[u] = ++cnt;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(ins[v]) low[u] = min(low[u], dfn[v]);
	}
}

割边、割点

一条边是割边满足，删了它之后，它所在的图不再联通。边 $(u,v)$ 是割边，有 $\mathrm{dfn}_u<\mathrm{low}_v$ 。

一条边是割点满足，删了它及其所有边之后，它所在的图被分成若干个连通块。点 $u$ 不是搜索树根节点，它是割点，有 $\exist v\in\mathrm{son}(u)\,\mathrm{dfn}_u\leq\mathrm{low}_v$ ；若是根节点则需满足两条。

边双、点双

边双：不存在割边的图。

点双：不存在割点的图。

强连通分量

有向图中任意两点 $(u,v)$ ，有简单路径 $u\rightarrow v,v\rightarrow u$ 。