双连通分量又称为重连通分量

分为

(1)边的双连通分量 EDCC ：极大的不含桥的连通区域（块）

性质:

        边的双连通分量不管删掉哪条边都是连通的

        任意两点之间都包含两条不相交的路径（充分必要）

(2)点的双连通分量 VDCC ：极大的不包含割点的连通分量（块）

性质：        

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

概念:桥定义为在无向图中，如果删掉一条边 整个图会变得不连通 则这个边称为桥

割点：在无向图中，如果把某个点和与这条边关联的边都删掉 整个图会变得不连通的话，则这个点就称为割点

两个割点之间的边不一定是桥 一个桥两边的点不一定是割点

点连通分量不一定是边连通分量 一个边连通分量不一定是点连通分量

边双连通分量解法

时间戳 dfn(x) low(x) (无向图不存在横叉边)

（1）如何找到桥 (x <----> y )

        桥等价于dfn(x) < low(y)

(2)如何找到所有的边双连通分量

        方法一：将所有的桥删掉

        方法二：用一个栈 dfn(x)==low(x)

1.冗余路径

395. 冗余路径 - AcWing题库

给定一个无向连通图，问最少加多少条边，使得该图变成一个边双连通分量

#include <bits/stdc++.h>
using namespace std;
const int N=5010,M=20010;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
bool is_brige[M];
int d[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u,int from)
{dfn[u]=low[u]=++timestamp;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(dfn[u]<low[j]){is_brige[i]=is_brige[i^1]=true;}}else if(i!=(from^1))low[u]=min(low[u],dfn[j]);}if(dfn[u]==low[u]){++dcc_cnt;int y;do{y=stk[top--];id[y]=dcc_cnt;}while(y!=u);}
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);while(m--){int a,b;cin>>a>>b;add(a,b),add(b,a);}tarjan(1,-1);for(int i=0;i<idx;i++){if(is_brige[i])d[id[e[i]]]++;}int res=0;for(int i=1;i<=dcc_cnt;i++)if(d[i]==1)res++;printf("%d\n",(res+1)/2);return 0;
}

点连通分量解法

dfn(x) low(x)

(1)如何求割点（x <----> y） 

low[y]>=dfn[x]

情况一：如果x不是根节点 那么x就是一个割点

情况二：如果x是根节点 至少有两个子节点满足yi low[yi]>=dfn[x]

 2.电力

信息学奥赛一本通（C++版）在线评测系统

1.统计连通块个数 cnt

2.依次枚举从哪个块中删

3.再枚举删除哪个点

4.删完以后看看那个连通块剩多少部分 设为s部分

那么答案就是s+cnt-1

怎么删点呢 如果dfn[x]<=low[y] 那么如果把x删掉 y就会单独出来（割点定义）

那么就是去删除割点 割点还要特判根节点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10010,M=30010;
int n,m,ans,root;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{dfn[u]=low[u]=++timestamp;//第一次遍历让她们都等于时间戳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++;//假如是割点，则连通块++}else  low[u]=min(low[u],dfn[j]);//更新一遍最小值}if(u!=root&&cnt) cnt++;//假如不是根，且连通块个数不为0，说明这个也是一个割点，则连通块个数+1ans=max(ans,cnt);//更新一遍最大值
}
int main()
{while(scanf("%d%d",&n,&m),n||m){memset(dfn,0,sizeof dfn);//清空，因为dfn兼具判重的作用memset(h,-1,sizeof h);//清空idx=timestamp=0;//清空状态while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}ans=0;int cnt=0;for(root=0;root<n;root++)//枚举每个为根if(!dfn[root])//假如不在任何一个连通块中{cnt++;//则新开个连通块tarjan(root);//遍历一遍}printf("%d\n",cnt+ans-1);}return 0;
}

(2)如何求点双连通分量

 

3.矿场搭建

给定一个无向图，问最少在几个点上设置出口，可以使得不管哪个点坍塌，其余所有点都可以与某个出口连通 

 这里的cnt-1是因为已经放了一个门在叶子节点了 所以是在cnt-1个点里面选一个门去放 所以是cnt-1而不是不包含割点

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1010,M=510;
int n,m,root;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
vector<int>dcc[N];
bool cut[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{dfn[u]=low[u]=++timestamp;//第一次遍历让她们都等于时间戳stk[++top]=u;if(u==root&&h[u]==-1)//假如是孤立点{dcc_cnt++;dcc[dcc_cnt].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++;//子树加1if(u!=root||cnt>1) cut[u]=true;//假如不为根或者子树为>1则为割点++dcc_cnt;int y;//求割点中的点，也即点连通块的点，并放进队列中去do{y=stk[top--];dcc[dcc_cnt].push_back(y);}while(y!=j);dcc[dcc_cnt].push_back(u);}}else  low[u]=min(low[u],dfn[j]);//更新一遍最小值}
}
int main()
{int T=1;while(cin>>m,m){for(int i=1;i<=dcc_cnt;i++) dcc[i].clear();//清空idx=n=timestamp=top=dcc_cnt=0;//初始化memset(cut,0,sizeof cut);//清空割点memset(dfn,0,sizeof dfn);//清空，因为dfn兼具判重的作用memset(h,-1,sizeof h);//清空while(m--){int a,b;scanf("%d%d",&a,&b);n=max(n,max(a,b));add(a,b),add(b,a);}for(root=1;root<=n;root++)//枚举每个为根if(!dfn[root])//假如不在任何一个连通块中tarjan(root);//遍历一遍int res=0;ull num=1;for(int i=1;i<=dcc_cnt;i++)//枚举每一个连通块{int cnt=0;int len=dcc[i].size();for(int j=0;j<len;j++)//枚举该连通块的点if(cut[dcc[i][j]])//假如是割点，则割点++cnt++;if(cnt==0&&len>1) res+=2,num*=len*(len-1)/2;//假如不是割点且点的数量大于1else if(cnt==0) res++;//假如不是割点点的数量为1,则为孤立点else if(cnt==1) res++,num*=len-1;//假如有一个割点}printf("Case %d: %d %llu\n",T++,res,num);}return 0;
}