对于一个无向图，如果任意两点至少存在两条点不重复（除起点和终点外无公共点）的路径，则这个图就是点双联通。
这个要求等价于任意两条边都存在于一个简单环（即同一个点不能在圈中出现两次）中，即内部无割点。
那么算法首先要求出割点。
从代码中可以看出：只要求出割点，就开始组一个bcc中。
如果割点两侧都不存在环的话会怎么处理呢？
代码中相邻的割点（或者是割点和根节点）也被当做一个bcc处理。
bccno[i]为点i所在的bcc序号，那么割点的bccno为多少呢？
割点的bccno没有意义，割点存在于多个bcc中。
割点：删除这个点后，联通分量增加，那么这个点就是割点。
在图的dfs搜索树中，非根节点u的子节点v没有方向边（dfs搜索树中后代指向祖先的边）返回u的祖先，那么u就是割点。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<stack>
#include<vector>
using namespace std;
const int MAXN=1e3+,INF=0x3f3f3f3f,MOD=1e9+;
int n;
int vis[MAXN][MAXN];
vector<int>G[MAXN];
int dfs_color=; ///dfs时间戳
int pre[MAXN],post[MAXN];
int bcc_cnt=; ///联通分量
int low[MAXN]; ///u及其后代所能连回的最早祖先的pre值
int iscut[MAXN]; ///割点
vector<pair<int,int> >birdge; ///桥
struct edge
{
int u,v;
};
stack<edge>S;
int bccno[MAXN]; ///点所在的双联通分量
vector<int>bcc[MAXN]; ///双联通分量
int dfs(int u,int fa)
{
int lowu=pre[u]=++dfs_color;
int child=;
for(int i=; i<G[u].size(); i++)
{
int v=G[u][i];
edge e=(edge)
{
u,v
};
if(!pre[v])
{
S.push(e);
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>=pre[u])
{
iscut[u]=true;
if(lowv>pre[u]) birdge.push_back(make_pair(u,v));
bcc_cnt++;
bcc[bcc_cnt].clear();
while(!S.empty())
{
edge x=S.top();
S.pop();
if(bccno[x.u]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.u);
bccno[x.u]=bcc_cnt;
}
if(bccno[x.v]!=bcc_cnt)
{
bcc[bcc_cnt].push_back(x.v);
bccno[x.v]=bcc_cnt;
}
if(x.u==u&&x.v==v) break;
}
}
}
else if(pre[v]<pre[u]&&v!=fa)
{
S.push(e);
lowu=min(lowu,pre[v]);
}
}
if(fa<&&child==) iscut[u]=;
low[u]=lowu;
return low[u];
}
void find_bcc()
{
bcc_cnt=;
dfs_color=;
memset(pre,,sizeof(pre));
memset(iscut,,sizeof(iscut));
memset(bccno,,sizeof(bccno));
for(int i=; i<=n; i++)
if(!pre[i]) dfs(i,-);
}
void init(int m)
{
memset(vis,,sizeof(vis));
for(int i=; i<=n; i++) G[i].clear();
birdge.clear();
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
}
int main()
{
int m;
while(scanf("%d%d",&n,&m))
{
init(m);
find_bcc();
for(int i=; i<=bcc_cnt; i++)
{
cout<<i<<":";
for(int j=; j<bcc[i].size(); j++)
cout<<bcc[i][j]<<" ";
cout<<endl;
}
}
return ;
}