转自：https://www.zhihu.com/question/40746887/answer/88428236
连通分量有三种∶边双连通分量，点双连通分量，强连通分量，前两种属于无向图，后一种属于有向图
定义：
双连通分量又分双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。
代码如下：
点双联通
struct Edge{
int u,v;
Edge(int _u,int _v):u(_u),v(_v){}
}edge[maxn];
int dfn[maxn],low[maxn],cut[maxn],bccno[maxn];
vector<int>gra[maxn],bcc[maxn];
stack<int>stk;
int cnt,bcnt; void tarjan(int f,int u){
dfn[u]=low[u]=++cnt;
int child=0;
int sz=gra[u].size();
for(int i=0;i<sz;i++){
int id=gra[u][i];
int v=edge[id].v;
if(!dfn[v]){
stk.push(id);
child++;
tarjan(u,v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
cut[u]=1;
bcc[++bcnt].clear();
while(1){
int id=stk.top();
stk.pop();
int uu=edge[id].u;
int vv=edge[id].v;
if(bccno[uu]!=bcnt){
bcc[bcnt].push_back(uu);
bccno[uu]=bcnt;
}
if(bccno[vv]!=bcnt){
bcc[bcnt].push_back(vv);
bccno[vv]=bcnt;
}
if(uu==u&&vv==v){
break;
}
}
}
}else if(dfn[v]<dfn[u]&&v!=f){
stk.push(id);
low[u]=min(low[u],dfn[v]);
}
}
if(f<0&&child==1){
cut[u]=0;
}
}
边双联通
struct Edge{
int u,v;
Edge(int _u,int _v):u(_u),v(_v){}
}edge[maxn];
int dfn[maxn],low[maxn],bccno[maxn];
vector<int>gra[maxn],bcc[maxn];
bool isb[maxn];
void tarjan(int f,int u){
dfn[u]=low[u]=++cnt;
int sz=gra[u].size();
for(int i=0;i<sz;i++){
int id=gra[u][i];
int v=edge[id].v;
if(!dfn[v]){
tarjan(u,v);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
isb[id]=isb[id^1]=1;
}
}else if(dfn[v]<dfn[u]&&v!=f){
low[u]=min(low[u],dfn[v]);
}
}
}
void dfs(int u){
dfn[u]=1;
bccno[u]=bcnt;
int sz=gra[u].size();
for(int i=0;i<sz;i++){
int id=gra[u][i];
int v=edge[id].v;
if(isb[id]){
continue;
}
if(!dfn[v]){
dfs(v);
}
}
}
int main(){
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(-1,i);
}
}
memset(dfn,0,sizeof(dfn));
for(int i=1;i<=n;i++){
if(!dfn[i]){
bcnt++;
dfs(i);
}
}
}