dfn[i]是i点的进入时间

low[i]是从i点出发，所能访问到的最早的进入时间

模板这些是无向图

点有 ≤\le，边是 <<。

割点

rt：cntson≥2,is cutnotrt:dfnu≤lowv,is cutrt：cnt_{son} \ge 2 ,is ~ cut\\ not_{rt}:dfn_u\le low_v ,is~ cut

边双联通分量

dfnu<lowvdfn_u < low_v 则 eu,v is bridgee_{u,v}~ is ~bridge

割边分开的剩下块就是边双联通分量。

注：

1
2
3
else if(i!=(from^1)){
	low[u]=min(low[u],low[v]);
}

特判的原因是要缩连通块，防止把祖先给更新掉；割点不用因为不用缩点。

点双连通分量

图是点双连通，存在当且仅当

  • 图的顶点数不超过 22。

  • 图中任意两点都同时包含在至少一个简单环中。其中“简单环”指的是不自交的环，也就是我们通常画出的环。

点双联通分量性质

  • 图中任意一个非割点都在且只在一个点双连通分量之中。

  • 图中任意一个割点都在至少两个点双联通分量中。

不删割点就行

__END__