上一篇博客我们介绍了割点和桥，本文我们继续学习与连通性有关的一些概念
边双连通分量
什么是边双连通分量？
在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u 和 v 边双连通，边双联通分量是极大的边双连通子图
怎么求边双连通分量？
由于边双连通分量中去除任意一条边后，分量依然是连通的，所以边双连通分量中没有桥，故原图的边双连通分量等价于删去桥边后边双连通分量即可
等等，这不是相当于把桥删去，求强连通分量吗？！
代码如下：
void tarjan(int u,int father){
dfn[u]=low[u]=++dfncnt;
for(auto v:g[u]){
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])bridges[u]=bridges[u^1]=true;
}else if(u!=(father^1))low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u){
vis[u]=1;
for(auto v:g[u]){
if(bridges[u])continue;
if(!vis[v])dfs(v);
}
}
int main(){
for(register int i=1;i<=n;++i)
if(!dfn[i])tarjan(i,i);
for(register int i=1;i<=n;++i)
if(!vis[i]){
dfs(i);
++dcccnt;
}
}
点双连通分量
什么是点双连通分量？
在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通，点双联通分量是极大的点双连通子图
怎么求点双连通分量？
我们需要知道几个性质：
1.两个点双最多只有一个公共点（即都有边与之相连的点,因为当它们有两个及以上公共点时，它们可以合并为一个新的点双
2.这个点在这两个点双和它形成的子图中是割点，因为当对于这个子图而言它不是一个割点时，这两个点双也可以合并为一个新的点双
读者可以自行证明，这里就不加赘述
进一步，我们可以发现，对于一个点双，它在DFS搜索树中的dfn值最小的点一定是割点或者树根
当这个点是割点时，它所属的点双必定不能向它的父亲方向包括更多点，当这个点是树根时，它的dfn是整棵树里最小的，如果有两个以上的子树，那么它是割点，否则它是属于它的直系儿子的点双
一个点双一定在这两类点的子树中，代码如下：
void tarjan(int u, int father) {
int son = 0;
low[u]=dfn[u]=++dfncnt;
s[++tp]=u;
for(auto v:g[u]){
if(!dfn[v]){
son++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
bcc++;
while(s[tp+1]!=v)ans[bcc].push_back(s[top--]);//将子树出栈
ans[bcc].push_back(u);//把割点/树根也丢到点双里
}
} else if(v!=fa)low[u]=min(low[u],dfn[v]);
}
if(fa==0&&son==0)ans[++bcc].push_back(u);//特判独立点
}