文章目錄

• • 代碼實現
  • 實際應用
  • • 1.有向圖
    • 另外：對于縮點之后的DAG的處理
    • 2.無向圖
    • 求法
    • • 細節(jié)
      • 細節(jié)：
  • 目錄：
  • 1.「POJ 3694」Network
  • 2.「2019 ICPC 橫濱站」
  • 3. P3225 [HNOI2012]礦場搭建
  • 4. 一本通 分離的路徑

代碼實現

所以其實就三個玩意 1.dfn[],low[],indx 2.stack<int>s,bool pd[] 3.scc[],scnt，col[]等我們要求的信息變量名 用處 dfn 記錄當前已經訪問了幾個節(jié)點 scc 記錄當前已經有了幾個強連通分量 dfn[ maxn ] 當前節(jié)點是第幾個被訪問到的 low[ maxn ] 當前節(jié)點所能訪問到的最小的 dfn[ ] scc[ maxn ] 記錄各個節(jié)點所屬于的強連通分量編號 s[ maxn ] 存儲可能構成強連通分量的節(jié)點的棧 top 存儲棧頂

那么我們如果要求scc這樣一個東西,應該是用什么結構呢？
思想其實并不是很難，就是我們要求SCC，將它放入dfs序中，發(fā)現它有一定的特點，那就是在搜索樹中的點，一定可以通向祖先，那他們就是一個scc，因為他們可以彼此到達。

所以我們要找最大的scc，那么就是要求出最小的祖先。
所以每個節(jié)點不用存下所有祖先，而只用存這一個就夠了。
所以有了low[]來存x的搜索樹內邊和最小的點。

那么肯定是要dfs的。

發(fā)現low[]=min(low[son]),min(dfn[to]）;

所以dfs回溯遞歸處理，該問題具有自相似性。

實際應用

可以分為兩類

1.有向圖

縮點之后變成了一個DAG，那么什么時候應該縮點呢，
例子：

“喜歡”是可以傳遞的——如果A喜歡B，B喜歡C，那么A也喜歡C

一旦我們逮捕了一個間諜，他手中掌握的情報都將歸我們所有，這樣就有可能逮捕新的間諜，掌握新的情報。

給定一個 n 個點 m 條邊有向圖，每個點有一個權值，求一條路徑，使路徑經過的點權值之和最大，允許多次通過同一個點和邊。

從S到T，可以重復走，求所有路徑中點權最大值與最小值的差。

P1407 我們已知n對夫妻的婚姻狀況，稱第i對夫妻的男方為Bi，女方為Gi。若某男Bi與某女Gj曾經交往過（無論是大學，高中，亦或是幼兒園階段，i≠j），則當某方與其配偶（即Bi與Gi或Bj與Gj）感情出現問題時，他們有私奔的可能性。不妨設Bi和其配偶Gi感情不和，于是Bi和Gj舊情復燃，進而Bj因被戴綠帽而感到不爽，聯(lián)系上了他的初戀情人Gk……一串串的離婚事件像多米諾骨牌一般接踵而至。若在Bi和Gi離婚的前提下，這2n個人最終依然能夠結合成n對情侶，那么我們稱婚姻i為不安全的，否則婚姻i就是安全的。

給定所需信息，你的任務是判斷每對婚姻是否安全。

總結 ：可以重復走，有傳遞性（即一個接一個）

另外：對于縮點之后的DAG的處理

1.DAG 一定存在一個或多個入度為0或出度為0的點。

2.可以進行拓撲排序，排序靠后的點不可能到達靠前的點。

3.DAG上的DP(期望等）

4.把入度為0的點與出度為0的點之間連邊，會變成一個SCC

2.無向圖

點雙連通：刪去任何一個點仍然連通邊雙連通：刪去任何一條邊仍然連通

（下面會簡稱為“點雙和邊雙”）

另一種定義是，任何兩點之間至少存在兩條不經過相同中間點（邊）的路徑

---

如果不滿足雙連通性

割點（割頂）：刪去后原圖不連通的頂點集合點雙連通：刪去任何一個點仍然連通邊雙連通：刪去任何一條邊仍然連通割邊（橋）：刪去后原圖不連通的邊集合

邊雙連通分量：刪去所有割邊，每個連通塊都是邊雙連通分量

一張圖的點雙連通分量之間可能有公共點，邊雙連通分量之間不可能有公共點（否則他們整體可以構成一個邊雙）

滿足點（邊）雙連通性的極大子圖稱為點（邊）雙連通分量

如果一條邊左邊是一個最大的邊雙連通子圖（邊雙），右邊是另一個最大的邊雙連通子圖（邊雙），那么這個邊就是沒有用的，刪去，這樣剩下的就是邊雙了

點雙與割點可能會有公共點。點雙和點雙之間可能會有公共點

割邊的兩端大多數情況下是割點，除了一邊只有一個點的情況

求法

割邊

• 不需要用到棧，因為不用存儲強連通分量。
• 割邊一定存在于樹邊上，否則存在另一條路徑。
• 注意low的定義有所變化，有向圖中l(wèi)ow只代表能到達的在棧中的節(jié)點的最小值。但在無向圖中，沒有棧的限制。
• dfn[u]<low[v]那么（u，v）即為割邊

細節(jié)

• 注意這里變成了嚴格小于，因為我們限制了指向父親的邊，那么若low等于dfn的話相當于存在一條回路。
• 但是要進行特判不能讓出去的點再次走同一個無向邊，否則low[to]必定等于dfn[x],沒有意義了，但是還要允許重邊訪問，所以我們應該記錄邊的編號。

割點

• 對于搜索樹中的根節(jié)點，兒子數大于等于2即為割點。
• 對于一般點：dfn[u]<=low[v]那么u就是割點
• 但是注意割邊兩邊一般是割點，但是特殊情況下一邊只有一個點，那就不是割點了。

細節(jié)：

• 引入了rt，son每次tarjan都要重新賦值。
• 小心pd[]=true,cnt++;這樣的語句，因為bool值本來可能已賦值過了。
• 分類討論！！！不要忘了。

目錄：

「POJ 3694」Network

• 邊雙縮點變成樹，在線查詢兩點之間邊的個數，然后再一次縮點。

「2019 ICPC 橫濱站」

• 邊雙在指定無向邊的方向之后一定可以變成強連通分量。

P3225 [HNOI2012]礦場搭建

1.「POJ 3694」Network

在線查詢一個無向圖，加入一條邊后減少了多少條橋。

2.「2019 ICPC 橫濱站」

給出一些起點和終點，判定把無向邊確定方向之后能否滿足每一個起點都可以走到對應的終點。

3. P3225 [HNOI2012]礦場搭建

題意：對于一個礦場可視作無向圖，現在已知任意礦場塌陷后，每一個點可以從出口逃出，那么最少在圖上建立幾個出口及方案數。
那么可以發(fā)現刪去一個點對于點雙仍然聯(lián)通，所以dfs每一個點雙，統(tǒng)計點雙中有多少割點。

可以發(fā)現，如果將點雙視為點，那么圖會變成一個樹，如果斷掉一個割點，相當于斷裂一條邊，所以只要在葉子節(jié)點上建立就可以了。

• 若沒有割點則建立一個，方案數為節(jié)點數。
• 若有一個割點則需要建立一個在非割點上，方案數為非割點的數目。
• 若有兩個割點則不需要建立。

4. 一本通 分離的路徑

給出一個無向連通圖，現在求出使每個點到其他點都有兩條完全不同的路徑最少還需要添加幾條邊。

可以發(fā)現這就是一個邊雙，那么對邊雙縮點，圖會變成一個樹，那么只要給兩個葉子節(jié)點連邊再縮點，就可以使新的樹葉子數減少二，所以共用(sum-1)/2。

注意各個題解都沒有注意到的是，如果兩個普通兩個葉子相連只能減少一個葉子，因為如果他們的lca有兩個兒子就會在他們的lca處新增一個葉子。所對葉子節(jié)點的選取是有要求的。

總結

以上是生活随笔為你收集整理的Tarjan缩点/边双/点双的全部內容，希望文章能夠幫你解決所遇到的問題。

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