題外話：
今天不想碼代碼了，知識(shí)普及的一天

注意：以下內(nèi)容是在無向圖的基礎(chǔ)上

無向圖的割點(diǎn)

很久之前就知道這些名詞
今天終于可以來填坑了。。。

如果將連通圖G中的某個(gè)點(diǎn)及和這個(gè)點(diǎn)相關(guān)的邊刪除后，將使連通分量數(shù)量增加，那么這個(gè)點(diǎn)就稱為圖G的割點(diǎn)或是接合點(diǎn)。
如果一個(gè)無向圖沒有割點(diǎn)，則這樣的圖被稱為雙連通圖。
關(guān)于圖的割點(diǎn)，有如下兩條性質(zhì)：

【性質(zhì)一】
如果深度優(yōu)先搜索樹的根節(jié)點(diǎn)至少有兩個(gè)以上的子節(jié)點(diǎn)，則根節(jié)點(diǎn)是割點(diǎn)。顯然去掉根節(jié)點(diǎn)后將得到以子節(jié)點(diǎn)為根結(jié)點(diǎn)的森林。

【性質(zhì)二】
在深度優(yōu)先搜索樹中，v存在一個(gè)子節(jié)點(diǎn)不能通過后向邊到達(dá)v的祖先節(jié)點(diǎn)，則節(jié)點(diǎn)v是割點(diǎn)。
也就是說從v的子節(jié)點(diǎn)開始沒有一條邊能夠回到v的祖先節(jié)點(diǎn)，那么當(dāng)去掉v時(shí)將會(huì)使得v的子孫節(jié)點(diǎn)與v的祖先節(jié)點(diǎn)之間失去聯(lián)系。必定會(huì)使得圖不再連通。

可以通過對圖的深度優(yōu)先搜索，
加上上面的兩條性質(zhì)來尋找圖中的割點(diǎn)。
在對圖進(jìn)行深度優(yōu)先搜索時(shí)，記錄下遍歷的順序pre_order，
則pre_order從小到大就代表了從根節(jié)點(diǎn)一直到葉子節(jié)點(diǎn)。
在遍歷的時(shí)候同時(shí)得出每一個(gè)節(jié)點(diǎn)通過自己或是子孫節(jié)點(diǎn)的后向邊（不是從父親直接來的邊）所能達(dá)到的最原始的祖先，
也就是pre_order最小的節(jié)點(diǎn)，記錄在back_order中。
那么如果一個(gè)節(jié)點(diǎn)的back_order>=父節(jié)點(diǎn)的pre_order，
說明該節(jié)點(diǎn)的子孫節(jié)點(diǎn)不存在一條后向邊到達(dá)父節(jié)點(diǎn)的祖先節(jié)點(diǎn)，則根據(jù)第二條性質(zhì)，該節(jié)點(diǎn)必是割點(diǎn)。

back_order的計(jì)算

由于back_order記錄的是節(jié)點(diǎn)所能返回到的最原始的祖先節(jié)點(diǎn)，
初始化back_order[v]=pre_order[v]，
及頂點(diǎn)v所能返回的最原始祖先就是自己。
在對v進(jìn)行深搜時(shí)，如果與v相鄰的下一個(gè)節(jié)點(diǎn)w沒被訪問過，說明(v,w)是生成樹上的邊，
那么back_order[v]就應(yīng)該是v和w中能返回到最原始祖先的點(diǎn)的back_order，
即back_order[v]=min(back_order[v],back_order[w])
如果w已經(jīng)被訪問過，說明w就是v的祖先，那么back_order[v]就應(yīng)該是v之前計(jì)算得到的所能返回的祖先節(jié)點(diǎn)與w之間最小的一個(gè)，
即back_order[v]=min(back-order[v],pre_order[w])。

int pre[N]; int back[N]; int dfs(int now,int fa) {int low=pre[now]=++tot; //時(shí)間戳++int ch=0; //子節(jié)點(diǎn)個(gè)數(shù) for (int i=st[now];i;i=way[i].nxt){int v=way[i].y;if (!pre[v]) //v是子節(jié)點(diǎn) {ch++;int lowv=dfs(v,now); //子節(jié)點(diǎn)能夠回溯到的最遠(yuǎn)祖先 low=min(low,lowv);if (lowv>=pre[now]) //存在一個(gè)子節(jié)點(diǎn)與祖先不聯(lián)通，now就是割點(diǎn) iscut[now]=1; //割點(diǎn) }else if (pre[v]<pre[now]&&v!=fa) //是祖先，但不是直接父親 { //說明low是之前計(jì)算得到的所能返回的祖先節(jié)點(diǎn) low=min(low,pre[v]);}}if (fa<0&&ch==1) iscut[now]=0; //性質(zhì)一的驗(yàn)證 back[now]=low;return low; }

注意

一定要寫v!=fa
因?yàn)檫?#xff08;u，fa）不是反向邊，而是dfs樹邊（fa，u）的第二次遍歷
pre的初始化是0，第一次調(diào)用時(shí)，fa的初始值是-1

附：訓(xùn)練指南（劉汝佳著）P312上有更詳盡的解釋

無向圖的橋

作為一種特殊情況，u為v的父節(jié)點(diǎn)，且low(v) < pre(u)
那么我們只要?jiǎng)h掉（u，v）這條邊就可以讓無向圖不連通了
滿足這個(gè)條件的邊叫做無向圖的橋
也就是說，我們知道了u是割點(diǎn)，而且（u，v）是橋、

int dfs(int now,int fa) {int ch=0;int low=pre[now]=++tt;for (int i=st[now];i;i=way[i].nxt){int v=way[i].y;if (!pre[v]){int lowv=dfs(v,now);low=min(low,lowv);ch++;if (lowv>pre[now]) //存在即合理 { //因?yàn)橹徽覙?#xff0c;所以在這里我就省去了割點(diǎn)的記錄an++;ans[an].x=min(now,v);ans[an].y=max(now,v); } }else if (pre[v]<pre[now]&&v!=fa){low=min(low,pre[v]);}}back[now]=low;return low; }

無向圖的雙連通分量

對于一個(gè)連通圖，如果任意兩點(diǎn)至少存在兩條“點(diǎn)不重復(fù)”的路徑，則說這個(gè)圖是點(diǎn)-雙連通的（一般簡稱雙連通）
這就相當(dāng)于任意兩條邊都在同一個(gè)簡單環(huán)中，即內(nèi)部無割點(diǎn)

類似的，如果任意兩個(gè)點(diǎn)至少存在“邊不重復(fù)”的路徑，我們說這個(gè)圖是邊-雙連通的。
即所有邊都不是橋

對于一張無向圖，點(diǎn)-雙連通的極大子圖稱為雙連通分量

邊-雙連通的極大子圖稱為邊雙連通分量(BCC)，
也就是說，在刪除所有的橋之后，每個(gè)連通分量對應(yīng)原圖中的一個(gè)邊-雙連通分量

下面給出點(diǎn)雙(BCC)的計(jì)算方法

int pre[N],iscut[N],bccno[N],tot=0,bcc_cut; vector bcc[N]; stack<node> S;int dfs(int now,int fa) {int low=pre[now]=++tot;int ch=0;for (int i=st[now];i;i=way[i].nxt){int v=way[i].y;node e=way[i];if (!pre[v]){S.push(e);ch++;int lowv=dfs(v,now);low=min(low,lowv);if (lowv>=pre[now]){iscut[now]=1;bcc_cnt++;bcc[bcc_cnt].clear;for (;;){node x=S.top();S.pop();if (bccno[x.x]!=bcc_cnt){bcc[bcc_cnt].push_back(x.x);bccno[x.x]=bcc_cnt;}if (bccno[x.y]!=bcc_cnt){bcc[bcc_cnt].push_back(x.y);bccno[x.y]=bcc_cnt;}if (x.x==now&&x.y==v) break;}}else if (pre[v]<pre[now]&&v!=fa){S.push(e);low=min(low,pre[v]);}}}if (fa<0&&ch==1) iscut[now]=0;return low; }void find_bcc(int n) {memset(pre,0,sizeof(pre));memset(iscut,0,sizeof(iscut));memset(bccno,0,sizeof(bccno));tot=bcc_cnt=0;for (int i=1;i<=n;i++) //森林 if (!pre[i])dfs(i,-1); }

邊雙的計(jì)算方法更簡單，分兩個(gè)步驟，
先作一次dfs標(biāo)記出所有的橋，然后再做一次dfs找出邊雙
因?yàn)檫呺p不能經(jīng)過橋而且兩個(gè)邊雙之間沒有公共點(diǎn)，
所以在dfs的時(shí)候只要保證不經(jīng)過橋即可

轉(zhuǎn)載于:https://www.cnblogs.com/wutongtong3117/p/7673121.html

總結(jié)

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

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