无向图的点、边双连通分量

有向图的强连通分量：寒假学习笔记【匠心制作，图文并茂】——1.20拓扑、强连通分量、缩点

点双连通分量

在这之前，先让我们了解几个概念。

• 割点：删除一个点和其连出的边后，原图会裂为多个不连通的部分，这个点叫做割点。
• 点双连通分量（v-dcc，简称点双）：极⼤不含割点的连通⼦图（和强连通分量的定义很像）。

OK，现在让我们进入正题：求点双连通分量。

其实，我们不难想到，既然点双是极大不含割点的连通子图，那么两个割点之间的部分应该就是一个点双，而割点本身则属于多个点双，那怎么找割点呢？

我们顺着强连通分量的想法往下，如果我们先跑了一遍 tarjan，那么我们就会得到每个点的 low 和 dfn 值，那对于一个点双它肯定长这样：

这说明了什么？说明割点的子节点是无法通过其他边与上面的点相连的，否则这个点就不是割点了，这说明割点的 low 值应该大于等于其 dfn 值，因为越往上，dfn 值就越小，low 值也就越小，只有在上面那种情况下 low 值才会大于等于 dfn 值。

当然，在上述情况中还有几个特例，例如目前搜查的这个点没有父亲节点（即根节点），那就要看满足上述条件的子树有多少个，如果只有一个，那它也不是割点，否则就是。而对于其他点，因为它们都有儿子节点与父亲结点，所以只要有满足上述条件的子树就行，不用管多少个。

找到割点了，现在该找点双了。很明显，割点及其子节点就是一个点双，而按照强连通分量的做法，一个点的子节点都会被保存在栈中，所以我们只需要一直弹出栈顶，直到弹到割点就行了。

注意，我们前面说过：一个割点属于多个点双。所以我们在把割点弹出之后还要再放回栈中。

还有一种方案，就是我们不弹出割点，直接手动加上割点就行了。

核心代码如下：

vector<int>v[N];
stack<int>st;
void v_dcc(int u,int fa)
{dfn[u]=low[u]=++ti;if(u==rt&&v[u].size()==0)//一个点自成点双{cnt++;vdcc[cnt].emplace_back(u);return;}st.emplace(u);int son=0,sum=0;for(auto i:v[u]){if(i==fa){sum++;//解决重边问题if(sum==1){continue;}}if(!dfn[i]){dfs(i,u);low[u]=min(low[u],low[i]);if(dfn[u]<=low[i])//因为割点可能有多个子树，所以每扫到一个子树就要算一遍{son++;if(son==1&&u!=rt||son>=2){cut[u]=true;//判断割点}cnt++;while(!st.empty()){int x=st.top();st.pop();vdcc[cnt].emplace_back(x);if(x==i){break;}}vdcc[cnt].emplace_back(u);//割点属于多个点双}}else{low[u]=min(low[u],dfn[i]);}}
}

边双连通分量

同样，在这之前，先了解几个概念：

• 桥：断开后会让图分裂成两个不连通的部分的线。
• 边双连通分量（e-dcc，简称边双）：极大不含桥的联通子图。

和上面的点双类似，边双也是在强联通分量的做法的基础上改进的，我们先画一个边双模版：

很显而易见了，如果一条边是一个桥，那么它以下的子树都无法通过别的边与上面向连通。

那么我们假设边 (x,y) 是一个桥（x 在 y 上面），根据上面的性质就可以很轻松的得出 dfn[x]<low[y]，因为上下不连通的嘛，所以下面的 low 值肯定会比上面的 dfn 值还大。

通过桥，我们可以找到第一种找 e-dcc 的方法：把所有的桥全部断开，剩下的就是 e-dcc，不过难度有亿点大。

现在让我们回想上面对于桥的性质的描述：

如果一条边是一个桥，那么它以下的子树都无法通过别的边与上面向连通。

这是不是很想我们讲强连通分量里面的一句话：

我们假设一个节点与它的子树形成了一个 SCC，那么它以及它的所有子树都不会通过返祖边与横叉边与其他点相连，而且一定会有返祖边与这个根节点相连。

难道说，找 e-dcc 和找 SCC 有什么本质上的联系吗？

答案是有。根据桥的性质我们可以知道：一个桥以下的子树的 low 是等于最顶上那个节点的 dfn 的（都分析了那么多遍了，这次应该自己看得懂了吧）。这跟 SCC 的求法几乎一模一样！

因此，我们就可以写出代码。

当然最后说一点：因为原图是一个无向图，所以并不存在前向边和横叉边，因为这些边都会通过一系列转化变成返祖边，因此 ins 数组就可以省去，因为所有的边被换成返祖边了之后，那些“祖先们”肯定只能和它下面的点形成 e-dcc，也就不存在会被提前“收服”的情况了。

核心代码如下：

vector<int>v[N],edcc[N];
stack<int>st;
void e_dcc(int x,int fa)
{dfn[x]=low[x]=++ti;st.emplace(x);int sum=0;for(auto i:v[x]){if(i==fa){sum++;if(sum==1)//判重边{continue;}low[x]=min(low[x],dfn[fa]);//否则更新}if(!dfn[i]){e_dcc(i,x);low[x]=min(low[x],low[i]);}else//不必再判{low[x]=min(low[x],dfn[i]);}}if(low[x]==dfn[x]){cnt++;while(1){int u=st.top();st.pop();edcc[cnt].emplace_back(u);if(u==x){break;}}}
}