强连通分量和点双连通分量

强连通分量和点双连通分量是图论中常见的两个概念。算法竞赛中，我们处理它们时都要使用 Tarjan 算法，因而这二者常常被混淆。强连通分量常常被缩点代称，而点双连通分量则常被割点代称。事实上，缩点和割点并不是一组对应的概念；缩点在点双连通分量中对应的概念是圆方树，割点在强连通分量中对应的概念是割边（桥）。因此，我们要么说“强连通分量和点双连通分量”，要么说“缩点和圆方树”，要么说“割边和割点”，但是不要说“缩点和割点”。人们常将缩点和割点并称的原因可能是洛谷，其关于构造强连通分量和点双连通分量的模板题的名称分别为“缩点”和“割点”，具有很强的误导性。尤其是“缩点”和“割点”都含有“点”字，容易让初学者以为它们是对应的概念，看不透二者的真正关系。

那么，强连通分量和点双连通分量的真正关系是什么呢？或者说，怎样才能最好地理解它们的相似性和差异性呢？

割边和割点的关系。强连通分量是割边分隔出的点集，点双连通分量是割点分割出的点集（特别地，割点本身同时属于它四周的点双连通分量）。因此它们都可以使用 Tarjan 算法处理。在 DFS 树上，一条边 $E$ 是割边当且仅当其儿子的子树中没有指向 $E$ 的祖先（注意这里不是子树外而是祖先，因为有向图的 DFS 树形态特别）的返祖边，一个结点 $V$ 是割点当且仅当其某个儿子的子树中没有指向 $V$ 的祖先的返祖边。删去强连通分量中的任何边得到的生成子图仍然连通（弱连通），删去点双连通分量中的任何结点得到的导出子图仍然连通。

有向图和无向图的关系。强连通分量在有向图中定义，点双连通分量在无向图中定义。“任意两个结点都能够互相到达的极大子图”这一定义不能够在无向图中定义强连通分量，因为这实际上指的是连通块；但我们可以用强连通分量的另一个定义“割边分割出的点集”在无向图中定义一个与强连通分量相似的概念，即边双连通分量。因此，“割边分割出的点集”是最适合强连通分量和边双连通分量的定义，它同时适用于有向图和无向图，而强连通分量“任意两个结点都能够互相到达的极大子图”和边双连通分量“删去任意边后任意两个结点仍然连通的极大子图”这两个常见定义则只适用于有向图或无向图。

对于有向图，我们发现，一个节点 $v$ 的父边是割边，当且仅当从 $v$ 出发无法离开 $v$ 的子树；一个节点 $v$ 是割点，当且仅当从 $v$ 出发，且不经过从 $v$ 出发的返祖边，无法离开 $v$ 的子树。

关于为什么求强连通分量可以写 low[node]=min(low[node],low[to]) 而求点双连通分量却只能写 low[node]=min(low[node],dfn[node] 的原因，想必读者也已经懂了。当然 low[node]=min(low[node],low[to]) 也不是一定就不能用于求割点，比如下面的代码就是可行的。

void dfs (int node) {
	dfn[node] = low[node] = ++ind;
	for (int i = head[node]; i; i = edge[i].next) {
		if (!dfn[edge[i].to]) {
			dfs(edge[i].to);
			if (low[edge[i].to] == dfn[node]) {
				is_cut[node] = true;
			}
		}
	}
    for (int i = head[node]; i; i = edge[i].next) {
        low[node] = std::min(low[node], low[edge[i].to]);
	}
}