文章目錄

• 無向圖割點(diǎn)、橋、雙連通分量
• • Tarjan算法求割點(diǎn)和橋（割邊）
  • 代碼：
  • 邊雙連通分量 和 點(diǎn)雙連通分量
  • 代碼
  • 邊雙連通分量 和 點(diǎn)雙連通分量 的縮點(diǎn)
• 有向圖的弱連通與強(qiáng)連通
• • 強(qiáng)連通分量
  • Kosaraju算法
  • Tarjan算法
  • 代碼：

無向圖割點(diǎn)、橋、雙連通分量

? 給定無向聯(lián)通圖G=（V,E） ? 對于一個(gè)點(diǎn)x，若從圖中刪除x及所有與x相連的邊，圖不再聯(lián)通，x是G的割點(diǎn)
? 對于一條邊e，從圖中刪去e，圖不再聯(lián)通，e的x的割邊
? 一個(gè)圖如果不存在割點(diǎn)，則它是一個(gè)點(diǎn)雙連通圖，一個(gè)圖的極大點(diǎn)雙連通子圖是他的點(diǎn)雙連
通分量。
? 一個(gè)圖如果不存在割邊，則它是一個(gè)邊雙連通圖，一個(gè)圖的極大邊雙連通子圖是他的邊雙連
通分量。

Tarjan算法求割點(diǎn)和橋（割邊）

時(shí)間戳dfn ：第n個(gè)搜到這個(gè)點(diǎn)
返祖邊：搜索樹上一個(gè)點(diǎn)連向其祖先節(jié)點(diǎn)的邊
橫插邊：搜索樹上一個(gè)點(diǎn)連向它另一條支鏈上的點(diǎn)的邊----在無向圖中不存在
追溯值low：當(dāng)前點(diǎn)及其子樹的返祖邊能連到的dfn值最小的點(diǎn)
如果<u,v>是搜索樹的邊：low[u]=min(low[u],low[v])


? u點(diǎn)是割點(diǎn)，v是u搜索樹上的一個(gè)兒子：dfn[u] <= low[v] ——v的子樹中沒有返祖邊能跨越u點(diǎn)；有多個(gè)兒子的根節(jié)點(diǎn)
比如圖中的點(diǎn)10和點(diǎn)7

? 邊是橋，搜索樹上v是u的兒子：dfn[u]<low[v]——v的子樹中沒有返祖邊能跨越<u,v>這條邊

代碼：

void tarjan(int x)//求割點(diǎn) {dfn[x]=low[x]=++cnt;int flag=0;for(int i=head[x];i;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);if(low[v]>=dfn[x]){flag++;if(x!=root||flag>1)book[x]=1;//flag>!說明根有兩個(gè)以上的兒子 }}else low[x]=min(low[x],dfn[v]);} }

求割邊：if(low[v] > dfn[x])

邊雙連通分量 和 點(diǎn)雙連通分量

? 把橋刪了每個(gè)連通塊都是一個(gè)邊雙聯(lián)通分量——標(biāo)記出橋之后dfs一遍即可
? 點(diǎn)雙連通分量要復(fù)雜一些——一個(gè)割點(diǎn)可能屬于多個(gè)雙聯(lián)通分量

點(diǎn)雙連通分量性質(zhì)：
任意兩點(diǎn)間至少存在兩條點(diǎn)不重復(fù)的路徑等價(jià)于圖中刪去任意一個(gè)點(diǎn)都不會改變圖的連通性，即BCC中無割點(diǎn)
若BCC間有公共點(diǎn)，則公共點(diǎn)為原圖的割點(diǎn)
無向連通圖中割點(diǎn)一定屬于至少兩個(gè)BCC，非割點(diǎn)只屬于一個(gè)BC

點(diǎn)雙連通分量求法:：
? 維護(hù)一個(gè)棧
? 第一次訪問某個(gè)節(jié)點(diǎn)時(shí)，將其入棧
? 當(dāng)割點(diǎn)判斷法則中dfn[x]<=low[y]成立時(shí)，不斷從棧中彈出節(jié)點(diǎn)，直到y(tǒng)被彈出，這些被彈出的點(diǎn)和x一起構(gòu)成一個(gè)點(diǎn)雙連通分量

代碼

#include<cstdio> #include<cctype> #include<vector> using namespace std; struct edge {int to,pre; }edges[1000001]; int head[1000001],dfn[1000001],dfs_clock,tot; int num;//BCC數(shù)量 int stack[1000001],top;//棧 vector<int>bcc[1000001]; int tarjan(int u,int fa) {int lowu=dfn[u]=++dfs_clock;for(int i=head[u];i;i=edges[i].pre)if(!dfn[edges[i].to]){stack[++top]=edges[i].to;//搜索到的點(diǎn)入棧 int lowv=tarjan(edges[i].to,u);lowu=min(lowu,lowv);if(lowv>=dfn[u])//是割點(diǎn)或根 {num++;while(stack[top]!=edges[i].to)//將點(diǎn)出棧直到目標(biāo)點(diǎn) bcc[num].push_back(stack[top--]);bcc[num].push_back(stack[top--]);//目標(biāo)點(diǎn)出棧 bcc[num].push_back(u);//不要忘了將當(dāng)前點(diǎn)存入bcc }}else if(edges[i].to!=fa)lowu=min(lowu,dfn[edges[i].to]);return lowu; } void add(int x,int y)//鄰接表存邊 {edges[++tot].to=y;edges[tot].pre=head[x];head[x]=tot; } int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y),add(y,x);}for(int i=1;i<=n;i++)//遍歷n個(gè)點(diǎn)tarjan if(!dfn[i]){stack[top=1]=i;tarjan(i,i);}for(int i=1;i<=num;i++){printf("BCC#%d: ",i);for(int j=0;j<bcc[i].size();j++)printf("%d ",bcc[i][j]);printf("\n");}return 0; }

邊雙連通分量 和 點(diǎn)雙連通分量 的縮點(diǎn)

? 每個(gè)邊雙連通分量縮成一個(gè)點(diǎn)，再用原來的橋把他們連起來
? 點(diǎn)雙聯(lián)通分量因?yàn)橐粋€(gè)割點(diǎn)可能包含在多個(gè)點(diǎn)雙連通分量里面，所以我們將每個(gè)割點(diǎn)保留割點(diǎn)與其所在的點(diǎn)雙連通分量連邊即可。

有向圖的弱連通與強(qiáng)連通

? 在有向圖G=（V，E）中，如果對于任意兩點(diǎn)u，v，存在一條從u到v或者從v到u的路徑——弱聯(lián)通
? 在有向圖G=（V，E）中，如果對于任意兩點(diǎn)u，v都互相可達(dá)——強(qiáng)聯(lián)通

強(qiáng)連通分量

? 有向圖強(qiáng)連通分量：在有向圖G中，如果兩個(gè)頂點(diǎn)vi,vj間（vi>vj）有一條從vi到vj的有向路
徑，同時(shí)還有一條從vj到vi的有向路徑，則稱兩個(gè)頂點(diǎn)強(qiáng)連通(strongly connected)。 ? 如果有向圖G的每兩個(gè)頂點(diǎn)都強(qiáng)連通，稱G是一個(gè)強(qiáng)連通圖。
? 有向圖的極大強(qiáng)連通子圖，稱為強(qiáng)連通分量(strongly connected components)。

Kosaraju算法

? 對原圖進(jìn)行一次dfs（任意起點(diǎn)）
? 在第一次形成的森林的每一顆樹里，以第一次搜索出棧時(shí)間的逆序?qū)Ψ磮D進(jìn)行dfs，這次搜索A能到達(dá)的點(diǎn)和A都在一個(gè)強(qiáng)連通分量里面

Tarjan算法

? Dfn[n]時(shí)間戳
? Low[n]他和他的子樹里返祖邊和橫叉邊能連到還沒出棧的dfn最小的點(diǎn)
? 在dfs的時(shí)候維護(hù)一個(gè)棧第一次訪問到某個(gè)點(diǎn)就將其加入到棧中，當(dāng)一個(gè)點(diǎn)x的dfn[x] == low[x] 時(shí)，他就是這個(gè)強(qiáng)連通分量里面在搜索樹中最高的點(diǎn)，將棧里點(diǎn)出棧直到x也出棧為止，這些點(diǎn)組成一個(gè)強(qiáng)連通分量。

代碼：

void tarjan(int x) {dfn[x]=low[x]=++cnt;stack[++top]=x;vis[x]=1;//x是否在棧里 for(int i=head[x];i;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[y]);}else if(vis[v])low[x]=min(low[x],dfn[v]);if(dfn[x]==low[x])//是否是強(qiáng)連通分量最高的點(diǎn) {ans++;//新強(qiáng)連通的標(biāo)號 do{int cur=stack[top--];//棧頂?shù)狞c(diǎn) vis[cur]=false;num[cur]=ans;}while(x!=cur);}}} 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的第1节 连通性强连通、割点和桥（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。