嗯，首先边双连通分量（双连通分量之一）是：在一个无向图中，去掉任意的一条边都不会改变此图的连通性，即不存在桥（连通两个边双连通分量的边），称作边双连通分量。一个无向图的每一个极大边双连通子图称作此无向图的双连通分量。
对于边连通分量，我们需要先找出所有的桥，即为所有的桥做上标记。
首先要用dfs的性质来快速找出一个连通图中的所有的桥。
时间戳：表示在进行dfs的时候，每个节点被访问的先后顺序。每个节点会被标记两次，分别用 pre[]，和post[]来表示。
在无向图中，只存在两种边，一种是树边（即边和点都没有被访问过），另一种是反向边（即边没有被访问过，但是点已经被访问过）。所以对于根节点而言，如果有两个及以上节点则根节点为割顶，否则不是
对于其他节点：在无向连通图G的DFS树中，非根节点u是割顶当且仅当u存在一个子节点v，使得v及其所有后代都没有反向边连回u的祖先（不包括u）
然后设low[u]为u及其后代所能连回的最早的祖先的pre[]值，则当u存在节点v使得low[v] >= pre[u]时，u 就为割顶；
而同理当 low[v] > pre[u] 时 u-v 是桥。
接下来直接上求图中割顶和桥的代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; const int maxn = ;
int n,m; //n为点数,m为边数
int dfs_time; //时间戳
vector<int>G[maxn];
int low[maxn],pre[maxn];
int iscut[maxn];//会标记是否为割顶 int dfs(int u,int fa){
int lowu = pre[u] = ++dfs_time;
int child = ;
for(int i = ;i < G[u].size();i++){
int v = G[u][i]; //v是u所连接的点
if(!pre[v]) //没有访问过
{
child++; //孩子的节点数
int lowv = dfs(v,u);
lowu = min(lowu,lowv); //用后代更新lowu //是割顶的判断条件
if(lowv >= pre[u])
iscut[u] = ; //是桥的判断条件
if(lowv > pre[u])
printf("%d -- %d 是桥\n",u,v);
}
else if(pre[v] < pre[u] && v != fa){
//是反向边的情况，就更新lowu
lowu = min(lowu,pre[v]);
}
return lowu; //返回当前节点及其子节点能回到的最早祖先的pre值
}
} int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(pre,,sizeof(pre));
memset(iscut,,sizeof(iscut));
for(int i = ;i <= n;i++)
G[i].clear();
int u,v; //u -> v
for(int i = ;i < m;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v); //在u中添加v
G[v].push_back(u); //在v中添加u（因为是无向图）
}
dfs(,-); //u是当前节点,fa是父节点
printf("割顶有：");
for(int i = ;i <= n;i++){
if(iscut[i]) //如果是割顶
printf("%d ",i);
}
}
return ;
}
第一步已经完成（对桥做标记）。然后利用dfs遍历连通分量，只不过在遍历的时候不能访问桥。
上代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std; const int maxn = ;
struct Edge
{
int no,v,next; //no：边的编号
}edges[maxn]; int n,m,ebcnum; //节点数目，无向边的数目，边_双连通分量的数目
int e,head[maxn];
int pre[maxn]; //第一次访问的时间戳
int dfs_clock; //时间戳
int isbridge[maxn]; //标记边是否为桥
vector<int> ebc[maxn]; //边_双连通分量 void addedges(int num,int u,int v) //加边
{
edges[e].no = num;
edges[e].v = v;
edges[e].next = head[u];
head[u] = e++;
edges[e].no = num++;
edges[e].v = u;
edges[e].next = head[v];
head[v] = e++;
} int dfs_findbridge(int u,int fa) //找出所有的桥
{
int lowu = pre[u] = ++dfs_clock;
for(int i=head[u];i!=-;i=edges[i].next)
{
int v = edges[i].v;
if(!pre[v])
{
int lowv = dfs_findbridge(v,u);
lowu = min(lowu,lowv);
if(lowv > pre[u])
{
isbridge[edges[i].no] = ; //桥
}
}
else if(pre[v] < pre[u] && v != fa)
{
lowu = min(lowu,pre[v]);
}
}
return lowu;
} void dfs_coutbridge(int u,int fa) //保存边_双连通分量的信息
{
ebc[ebcnum].push_back(u);
pre[u] = ++dfs_clock;
for(int i=head[u];i!=-;i=edges[i].next)
{
int v = edges[i].v;
if(!isbridge[edges[i].no] && !pre[v]) dfs_coutbridge(v,u);
}
} void init()
{
memset(pre,,sizeof(pre));
memset(isbridge,,sizeof(isbridge));
memset(head,-,sizeof(head));
e = ;
ebcnum = ;
} int main()
{
int u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(int i=;i<m;i++)
{
scanf("%d%d",&u,&v);
addedges(i,u,v);
}
dfs_findbridge(,-); //进行找桥
memset(pre,,sizeof(pre));
for(int i=;i<=n;i++)
{
if(!pre[i])
{
ebc[ebcnum].clear();
dfs_coutbridge(i,-);
ebcnum++;
}
}
for(int i=;i<ebcnum;i++)
{
for(int j=;j<ebc[i].size();j++)
printf("%d ",ebc[i][j]);
printf("\n");
}
}
return ;
}