• 總算把這幾個東西策清楚了。

• 在\(Tarjan\)算法里面，有兩個時間戳非常重要，一個是\(dfn\)，意為深度優先數，即代表訪問順序；一個是\(low\)，意為通過反向邊能到達的最小\(dfn\)，也就是最強反祖能力。

• 注意，強聯通分量只存在于有向圖中，割點，橋，點雙，邊雙是無向圖的概念。

一、割點。

• [x] 模板題
• 割點：一個結點稱為割點，當且僅當去掉該節點和其相關的邊之后的子圖不連通。
• 針對無向圖。
• 首先我們考慮一個連通圖（非連通圖可以分別考慮連通塊），我們從任意一個起點開始進行深度優先搜索，可以得到一棵樹，并且這棵樹中所有結點的子樹之間不存在邊，即沒有跨越兩棵子樹的邊
• 考慮一下，如果存在，那么與深度優先搜索樹的定義互相矛盾。

• 于是有如下定理：
  在無向連通圖\(G\)中，
  1、根結點\(u\)為割頂當且僅當它有兩個或者多個子結點；
  2、非根結點\(u\)為割頂當且僅當u存在結點v，使得\(v\)與其所有后代都沒有反向邊可以連回\(u\)的祖先。可以簡單寫成\(dfn_u\leq low_v\)

• 貼個代碼

void Tarjan(R i,R rt){R sum=0;dfn[i]=low[i]=(++cnt);for(R k=hd[i];k;k=nt[k]){if(!dfn[to[k]]){Tarjan(to[k],rt),low[i]=min(low[i],low[to[k]]);if(i==rt)sum++;else if(low[to[k]]>=dfn[i])ans[i]=1;}else low[i]=min(low[i],dfn[to[k]]);}if(i==rt&&sum>1)ans[i]=1; }注意 在不聯通圖中，應當 for(R i=1;i<=n;++i)if(!dfn[i])Tarjan(i,i); 這樣才能保證全部求到，注意根節點.

二、橋。

• 針對無向圖。
• 橋的求法其實也是類似的，它的求法可以看成是割頂的一種特殊情況.
• 當結點\(u\)的子結點\(v\)的后代通過反向邊只能連回\(v\)，那么刪除這條邊\((u, v)\)就可以使得圖\(G\)非連通了。用\(Tarjan\)算法里面的時間戳表示這個條件，就是\(low_v>dfn_u\)。
• 注意更新\(low\)時是特判不能使用來的反邊。
• 不需要單獨考慮根節點的情況。
• 貼個代碼

void Tarjan(R i,R id){dfn[i]=low[i]=(++cnt);for(R k=hd[i];k;k=nt[k]){if(k==(id^1))continue; 無向圖中，這樣的邊是不能被遍歷的。if(!dfn[to[k]]){Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);if(low[to[k]]>dfn[i])G[++tot]=k; k這條邊即為橋。}else low[i]=min(low[i],dfn[to[k]]);} }

三、強聯通和雙聯通一點區別。

• 鏈接

• 所謂雙連通與強連通，最大的差別，也是最本質的差別就是后者適用于無向圖中，而前者適用于有向圖。至于兩者的概念是一樣的，就是圖中有a點、b點，從a點可到達b點，同時從b點可到達a點。

四、強聯通分量。

• 而為了存儲整個強聯通分量，這里挑選的容器是棧。
• 每次一個新節點出現，就進，如果這個點有出度就繼續往下找。
• 每次返回上來都看一看子節點與這個節點的\(low\)值，誰小就取誰，保證最小的子樹根。
• 如果找到\(low==dfn\)，說明這個節點是這個分量的根節點。

• 最后找到分量的節點后，就將這個棧里，它們就組成一個全新的分量。

• 具體實現的時候，如果這條邊是往下的邊，就用他的\(low\)去更新現在的\(low\)

• 否則，如果這條邊指向了棧內的點，就用他的\(dfn\)去更新現在的\(low\)

• 為什么要特別判斷是否是棧內的點呢？因為只有棧內的點才可以到達當前點。在有向圖中，如果指向的點不在棧內，他也就無法到達當前點，不可能組成強聯通。

• 判斷\(low==dfn\)是在\(for\)循環外面進行的。

• 貼個代碼

void Tarjan(R i){low[i]=dfn[i]=(++cnt),vis[i]=1,Q[++tp]=i;R p=tp;for(R k=hd[i];k;k=nt[k]){if(!dfn[to[k]])Tarjan(to[k]),low[i]=min(low[i],low[to[k]]);else if(vis[to[k]])low[i]=min(low[i],dfn[to[k]]);}if(dfn[i]==low[i]){tot++;for(R j=p;j<=top;++j)vis[Q[j]]=0,bel[Q[j]]=tot;tp=p-1;} }

五、邊雙。

• 其實就是一個求橋的過程。
• 一個橋把聯通塊分成了兩個部分，這兩個部分是獨立的兩個邊雙。
• 貼個代碼

void Tarjan(R i,R id){dfn[i]=low[i]=(++cnt);for(R k=hd[i];k;k=nt[k]){if(k==(id^1))continue; if(!dfn[to[k]]){Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);if(low[to[k]]>dfn[i])vis[k]=vis[k^1]=1; 標記}else low[i]=min(low[i],dfn[to[k]]);} }

upd on 10.31

• 另外一種寫法：
• 或者類似于有向圖的強聯通分量，區別在于：
• 強制不走回頭路。
• 不需要考慮是否在棧內。

void Tarjan(R i,R op){low[i]=dfn[i]=(++cnt),Q[++tp]=i;R p=tp;for(R k=hd[i];k;k=nt[k]){if(k==op^1)continue;if(!dfn[to[k]])Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);else low[i]=min(low[i],dfn[to[k]]);}if(dfn[i]==low[i]){tot++;for(R j=p;j<=top;++j)bel[Q[j]]=tot;tp=p-1;} }

六、點雙

• 其實就是一個求割點的過程。
• 一個割點把聯通塊分成了兩個部分，這兩個部分是獨立的兩個點雙。
• 貼個代碼

void Tarjan(R i,R rt){R sum=0;dfn[i]=low[i]=(++cnt);for(R k=hd[i];k;k=nt[k]){if(!dfn[to[k]]){Tarjan(to[k],rt),low[i]=min(low[i],low[to[k]]);if(i==rt)sum++;else if(low[to[k]]>=dfn[i])ans[i]=1;}else low[i]=min(low[i],dfn[to[k]]);}if(i==rt&&sum>1)ans[i]=1; }

• 和割點的代碼是一樣的，只是最后\(Dfs\)找到所有點雙，注意，一個割點會存在于多個點雙內。

  七、小清新水題。

• [x] 割點模板題
• [x] 橋模板題
• [x] 有向圖強聯通分量模板

• [x] 無向圖邊雙模板

• 其他題目在yl題單了。

轉載于:https://www.cnblogs.com/Tyher/p/9843020.html

總結

以上是生活随笔為你收集整理的Tarjan 复习小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。