双连通分量---图中不包含割点的连通分量

[UNICKCHENG]

双连通分量

待更新题库

[任务] 给定一个无向图,求出它的双连通分量 [说明] 和求割点类似的方法,在对图DFS的时候记录low和dfn,由于一个点可以属于多个双连通分量,而一条边属于唯一的双连通分量,所以我们用一个边集来描述一个双连通分量,即属于这个边集的所有边加上这些边的端点构成一个双连通分量 每次我们发现一条树边(从父节点指向未被访问的子节点)和回边(从子节点指向父节点),就将它压入栈中.当DFS从节点u返回到节点v时,如果low[u]>=dfn[v],那么我们就不断地将栈顶的边弹出,直到弹出边(v,u)为止,所有弹出的边构成一个双连通分量 [接口] void biconnect(int n) 复杂度:O(|E|+|V|) 输入     v DFS到当前节点     edge 全局变量,edge[i]表示从点i连出去的边 输出     connect 全局变量,表示各个双连通分量

const int maxn=1010;
vector<int> edge[maxn];
vector<vector<int>> connect;
int dfn[maxn],low[maxn],in_seq[maxn];
int stack[maxn],list[maxn];
int cnt,top,pop,len;
void biconnect(int v)
{
stack[++top]=v;
dfn[v]=low[v]=pop++;
int i,succ;
for(i=edge[v].size()-1;i>=0;i--)
{
succ=edge[v][i];
if(dfn[succ]==-1)
{
biconnect(succ);
if(low[succ]>=dfn[v])
{
cnt++;
len=0;
do{
in_seq[stack[top]]=cnt;
list[len++]=stack[top];
top--;
}while(stack[top+1]!=succ);
in_seq[v]=cnt;
list[len++]=v;
vector<int> tmp(list,list+len);
connect.push_back(tmp);
}
low[v]=min(low[v],low[succ]);
}
else low[v]=min(low[v],dfn[succ]);
}
}

题库

ID	TITLE	CODE(C/C++)	备注
POJ2942	Knights of the Round Table	查看代码