无向图的双连通分量

又称重连通分量，分为两大类边的双连通分量(e-DCC)，点的双连通分量(v-DCC)

e-DCC:极大的，不含桥的连通块

桥：对于一个连通的无向图，去掉某一条边后，变得不再连通，那么这条边就被称为桥.

在边的双连通分量中，任意两点之间一定包含两条不相交的路径（边不相交，点可以相交，相交即公共）

v-DCC：极大的，不含割点的连通块（简称块）

割点：在一个连通图中删掉某个点及与它关联的边后图变得不连通，那么这个点就是割点。

 每个割点至少属于两个连通分量

但是在一个点的双连通分量中，去除任意一个点图仍是连通的，其中的点仅仅是对于该连通分量来说不是割点，对于整张图来说可能是割点。

 两个割点之间的边不一定是桥，任何一个桥的两个端点不一定是割点。点连通分量不一定是边连通分量，边连通分量不一定是点连通分量。

tarjan算法求边的双连通分量：

类似有有向图中的做法，定义时间戳dfn[u]，low[u],

如何找到桥：x是y的父节点，如果dfn[x]<low[y],那么x,y之间的边就是桥

如何找到所有的边的双连通分量：

1.去掉所有的桥，然后剩下的连通块就是

2.将当前遍历到的都存进栈，当dfn[u]==low[u]时，栈中存的就是一个边的双连通分量。

我们还是结合具体的例题来看吧：
395. 冗余路径（395. 冗余路径 - AcWing题库）

本题的突破点在于任意一对点之间都至少两条相互分离的路径，按照题目要求相互分离就是边不重复，点是可以重复的。

那么图中就没有桥，也即去除任意一条路径后仍是连通的。我们可以通过求无向图的边连通分量来实现，一个边连通分量内部显然是满足条件的，我们将它缩成一个点，那么最终可以得到一棵树，我们添加的道路实际上就是叶子节点的数目/2上取整，即将叶子节点之间联系起来。

在求边连通分量的时候和求强连通分量很像，不过我们需要记录一下桥边，另外在无向图中是没有横叉边的，所以我们第二种类型的更新不是判断点是否在栈中，而是判断当前访问到的边是不是转移到这个点的边。统计的时候遍历所有的边，如果这条边是桥，那么就将它的入点所在的连通分量的入度加1，因为建的是双向边，所以最后只有叶子节点的度数是1.

#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=20010;
int n,m;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfn[N],low[N],stk[N],st[N],isdge[M],id[N],tp,top,dcc;
int d[N];
void tarjan(int u,int from)
{dfn[u]=low[u]=++tp;stk[++top]=u;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(!dfn[j]){tarjan(j,i);low[u]=min(low[u],low[j]);if(low[j]>dfn[u])isdge[i]=isdge[i^1]=1;//01一对，23一对，所以对一取异或就是反向边的下标}else if(i!=(from^1))//不是来边的反向边low[u]=min(low[u],dfn[j]);}if(low[u]==dfn[u]){int y;dcc++;do{y=stk[top--];id[y]=dcc;}while(y!=u);}
}
int main()
{scanf("%d%d",&n,&m);memset(h,-1,sizeof h);for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}tarjan(1,-1);for(int i=0;i<idx;i++)if(isdge[i])d[id[e[i]]]++;int cnt=0;for(int i=1;i<=dcc;i++)if(d[i]==1) cnt++;printf("%d",(cnt+1)/2);
}

点连通分量：

还是引入时间戳dfn[u],low[u];

点连通分量这块儿涉及到两个问题：

如何求割点：

x是y的父节点，当low[y]>=dfn[x]的时候：

如果x不是根节点，那么去掉x后，x的子树和x的父节点就不连通了，那么x就是割点

如果x是根节点，那么至少有两个子节点，那么x也是割点

找割点和找e-dcc有点像，但是第二次更新是没有任何限制条件的，找e-dcc的时候，不能用树枝边来更新，但是找割点的时候就无所谓，因为割点是属于至少两个连通块的。或者换个角度看，vdcc在判断的时候必须严格大于，而割点判断的时候是可以等于的。

如何求点的双连通分量：

这里框架和求割点的框架实际上差不多，但是由于我们需要记录每个点的双连通分量中有哪些点，所以需要用到栈来记录，当low[y]>=dfn[x]的时候，说明找到了一个双连通分量，将栈中的元素弹出放入容器，弹到y为止，然后再将x放入容器。

可能会产生疑惑，当等号成立的时候，x自然属于这个连通分量没问题，但是当严格小于的时候，好像不成立，但是注意到严格小于的时候，y的那一块儿会满足条件提前弹一次，那么栈中就剩下y了，所以实际上这时记录的分量中只有x和y，然后把y弹出，不会影响x的下一个分支的统计，

伪代码：

//孤立点特判
if(x==root&&h[x]==-1) x是一个双连通分量//常规情况的判断和处理
if(dfn[x]<=low[y])
{cnt++;if(x非根||cnt>1) x是割点 将栈中元素弹出一直到y为止且x也属于该点双连通分量
}

1183. 电力(活动 - AcWing)

思路： 本题要求删除一个点之后还剩多少连通块，首先在连通块内部删除一个点，对其他的连通块是不产生影响的，那么就需要考虑删除这个后在连通块内部产生多少个新的部分，首先如果这个点不是割点，而是属于一个连通分量中，那么删除之后也不会产生任何影响，所以只有割点被删除才会产生影响，所以问题的核心就是找割点，那么就可以直接用tarjan算法了，不过还有一点比较麻烦的在于还需要判断这个点是否是根节点，如果不是根节点，那么删除后除了子树还需要多一个连通块。

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=30010;
int n,m;
int ans;
int root;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],tp;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{int cnt=0;dfn[u]=low[u]=++tp;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(!dfn[j]){tarjan(j);low[u]=min(low[u],low[j]);if(low[j]>=dfn[u]) cnt++;//当前点是割点，以j为根节点有一棵子树}else low[u]=min(low[u],dfn[j]);}if(u!=root) cnt++;ans=max(cnt,ans);
}
int main()
{while(~scanf("%d%d",&n,&m)){if(!n&&!m) break;memset(h,-1,sizeof h);memset(dfn,0,sizeof dfn);tp=idx=0;for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}ans=0;int c=0;for(root=0;root<n;root++)if(!dfn[root]) {    c++;tarjan(root);}cout<<c-1+ans<<endl;}}

396. 矿场搭建（396. 矿场搭建 - AcWing题库）

无向图，需要设置一些救生点，使得无论哪个矿点坍塌都有出口可以出去。最明显的一点就是两个连通块之间不能相互到达，所以它们可以被分开讨论。那么我们先看一个连通块内部，那么我们可以从点的双连通分量的角度来考虑，算出来所有的点的双连通分量后显然需要进行缩点，那么该如何缩点呢？这里比较特殊，我们将点的双连通分量视为一个点，将割点也视为一个点，那么就可以得到一张新图：

如图，对于左右两个红点，我们要在它们内部设置一个救生点（不能设在割点位置），这样哪怕割点坍塌，它们可以内部自救，对于中间那个红点，它有两个割点，那么就无所谓了，从哪里都可以逃生。

我们一个一个连通块看的时候，本质上也是一个连通分量一个连通分量来看的，所以我们直接来看每个连通分量，对于一个连通分量，如果没有割点的话，那么随便设置2个救生点即可（一个坍塌了可以从另一个逃）；如果有一个割点的话，只要在非割点位置设置一个逃生点就好（割点坍塌内部自救，割点没塌从割点逃到别的连通分量中）；如果有大于等于两个割点，那么就无所谓，不用设置，可以从任意一个没塌的割点逃出去。

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1200;
typedef unsigned long long ull;
int n,m;
int root;
int dfn[N],low[N],stk[N],cut[N];
int tp,top,vdcc;
vector<int>q[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{dfn[u]=low[u]=++tp;stk[++top]=u;if(u==root&&h[u]==-1)//孤立点特判{vdcc++;q[vdcc].push_back(u);return;}int cnt=0;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(!dfn[j]){tarjan(j);low[u]=min(low[u],low[j]);if(low[j]>=dfn[u]){cnt++;if(u!=root||cnt>1) cut[u]=1;++vdcc;int y;do{y=stk[top--];q[vdcc].push_back(y);}while(y!=j);q[vdcc].push_back(u);}}else low[u]=min(low[u],dfn[j]);}
}
int main()
{int t=0;while(~scanf("%d",&m)){if(m==0) break;t++;for(int i=1;i<=vdcc;i++) q[i].clear();memset(h,-1,sizeof h);memset(dfn,0,sizeof dfn);memset(cut,0,sizeof cut);top=vdcc=tp=idx=n=0;for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);n=max(n,a),n=max(b,n);add(a,b),add(b,a);}for(root=1;root<=n;root++)if(!dfn[root])tarjan(root);int res=0;ull f=1;        for(int i=1;i<=vdcc;i++){int cnt=0;for(int j=0;j<q[i].size();j++)if(cut[q[i][j]]) cnt++;int l=q[i].size();if(cnt==0){if(l>=2) res += 2,f *= (l)*(l-1)/2;else res += 1;}else if(cnt==1){res += 1;f *= l-1;}}printf("Case %d: %d %llu\n",t,res,f);}
}

一定要注意边的双连通分量和点的双连通分量更新和判断的条件是不一样的。