无向图：桥和割点
桥的概念：无向图删去边e后分裂成两个不相连的子图
割点概念：无向图删去点v以及和v相连的所有边后分裂成两个及以上的子图
一些概念：
搜索树：在无向图中任意选择一点作为起点进行dfs，每个点访问一次，每次发生递归的边（x，y），即访问到之前没有访问到的点所经过的边，组成的搜索树
时间戳：在dfs过程中无向图中的结点被访问到的时间，用dfn数组来表示
追溯值：用low数组表示追溯值，low[x]定义为以下结点的时间戳的最小值：
1.x 子孙结点的时间戳
2.x子孙能通过非搜索树上的边所达到的点的时间戳
桥的判定法则：无向边(x,y)是桥 <==> 搜索树上存在x的一个子节点y，有dfn[x]<low[y]
推论：桥一定是搜索树中的边，一个简单环中的边一定都不是桥
割点的判定法则：如果x是root，那么如果x有两个及以上儿子，x就是割点
如果x非root，那么如果搜索树上存在x的一个子节点y，有dfs[x]<=low[y]，那么x就是割点
求桥时要特别注意一下重边和父边！
下面是求桥和割点的代码
void Tarjanb(int u,int pre){ low[u]=dfn[u]=++index; int son=0,pre_cnt=0;//处理重边和回边 for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v==pre&&pre_cnt==0){ pre_cnt++;continue; } if(!dfn[v]){//如果v未被访问过 son++; Tarjan(v,u); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]){//桥 bridge++; edge[i].cut=true; edge[i^1].cut=true; } if(u!=pre && dfn[u]<=low[v]){//非树根的割点 cut[u]=true; add_block[u]++; } } else low[u]=min(low[u],dfn[v]);//v被访问过了 } if(u==pre && son>1)cut[u]=true;//树根割点 if(u==pre)add_block[u]=son-1; }
无向图：双联通分量
点双联通图：无向连通图不存在割点
边双联通图：无向连通图不存在桥
点双联通分量：无向图的极大点双联通子图v-DCC
边双联通分量：无向图的极大边双联通子图e-DCC
定理
点双联通图的判定条件：
1.图的顶点数不超过2
2.图中任意两点至少包含在一个简单环中
边双联通图的判定条件：
1.图中任意一条边都包含在一个简单环中
e-DCC的求法：只要求出图中所有桥，把桥删掉后图分裂成的联通块就是e-DCC
先把桥都求出来，然后一次dfs进行染色，数组c[x]表示x所在的联通块的编号
int c[maxn],dcc; void dfs(int u){ c[u]=dcc; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(c[v] || bridge[i])continue;//碰到桥就不往下dfs dfs(v); } } int main(){ //... dcc=0; for(int i=1;i<=n;i++) if(!c[i]){ ++dcc; dfs(i); } //... }
e-DCC的缩点法，把每个边双联通分量缩成一个点，将原图变成一棵树或森林，存在新的邻接表中
这个过程中同样可以求出每个缩点的度数
struct Edge{ int to,nxt; }edge_c[maxn<<1]; int head_c[maxn],tot_c; void init(){ memset(head_c,-1,sizeof head_c); tot_c=0; } void add_c(int u,int v){ edge_c[tot_c].to=v; edge_c[tot_c].nxt=head_c[u]; head_c[u]=tot_c++; } int main(){ //... for(int i=0;i<tot;i+=2){ int v=edge[i].to,u=edge[i^1].to;//无向图的两条边一定连在一起 if(c[u]==c[v])continue; add_c(c[u],c[v]); } //... }
原文：https://www.cnblogs.com/zsben991126/p/10454158.html