有向圖的強連通分量：寒假學習筆記【匠心制作，圖文并茂】——1.20拓撲、強連通分量、縮點

點雙連通分量

在這之前，先讓我們了解幾個概念。

• 割點：刪除一個點和其連出的邊后，原圖會裂為多個不連通的部分，這個點叫做割點。
• 點雙連通分量（v-dcc，簡稱點雙）：極?不含割點的連通?圖（和強連通分量的定義很像）。

OK，現在讓我們進入正題：求點雙連通分量。

其實，我們不難想到，既然點雙是極大不含割點的連通子圖，那么兩個割點之間的部分應該就是一個點雙，而割點本身則屬于多個點雙，那怎么找割點呢？

我們順著強連通分量的想法往下，如果我們先跑了一遍 tarjan，那么我們就會得到每個點的 low 和 dfn 值，那對于一個點雙它肯定長這樣：

這說明了什么？說明割點的子節點是無法通過其他邊與上面的點相連的，否則這個點就不是割點了，這說明割點的 low 值應該大于等于其 dfn 值，因為越往上，dfn 值就越小，low 值也就越小，只有在上面那種情況下 low 值才會大于等于 dfn 值。

當然，在上述情況中還有幾個特例，例如目前搜查的這個點沒有父親節點（即根節點），那就要看滿足上述條件的子樹有多少個，如果只有一個，那它也不是割點，否則就是。而對于其他點，因為它們都有兒子節點與父親結點，所以只要有滿足上述條件的子樹就行，不用管多少個。

找到割點了，現在該找點雙了。很明顯，割點及其子節點就是一個點雙，而按照強連通分量的做法，一個點的子節點都會被保存在棧中，所以我們只需要一直彈出棧頂，直到彈到割點就行了。

注意，我們前面說過：一個割點屬于多個點雙。所以我們在把割點彈出之后還要再放回棧中。

還有一種方案，就是我們不彈出割點，直接手動加上割點就行了。

核心代碼如下：

vector<int>v[N];
stack<int>st;
void v_dcc(int u,int fa)
{dfn[u]=low[u]=++ti;if(u==rt&&v[u].size()==0)//一個點自成點雙{cnt++;vdcc[cnt].emplace_back(u);return;}st.emplace(u);int son=0,sum=0;for(auto i:v[u]){if(i==fa){sum++;//解決重邊問題if(sum==1){continue;}}if(!dfn[i]){dfs(i,u);low[u]=min(low[u],low[i]);if(dfn[u]<=low[i])//因為割點可能有多個子樹，所以每掃到一個子樹就要算一遍{son++;if(son==1&&u!=rt||son>=2){cut[u]=true;//判斷割點}cnt++;while(!st.empty()){int x=st.top();st.pop();vdcc[cnt].emplace_back(x);if(x==i){break;}}vdcc[cnt].emplace_back(u);//割點屬于多個點雙}}else{low[u]=min(low[u],dfn[i]);}}
}

邊雙連通分量

同樣，在這之前，先了解幾個概念：

• 橋：斷開后會讓圖分裂成兩個不連通的部分的線。
• 邊雙連通分量（e-dcc，簡稱邊雙）：極大不含橋的聯通子圖。

和上面的點雙類似，邊雙也是在強聯通分量的做法的基礎上改進的，我們先畫一個邊雙模版：

很顯而易見了，如果一條邊是一個橋，那么它以下的子樹都無法通過別的邊與上面向連通。

那么我們假設邊 (x,y) 是一個橋（x 在 y 上面），根據上面的性質就可以很輕松的得出 dfn[x]<low[y]，因為上下不連通的嘛，所以下面的 low 值肯定會比上面的 dfn 值還大。

通過橋，我們可以找到第一種找 e-dcc 的方法：把所有的橋全部斷開，剩下的就是 e-dcc，不過難度有億點大。

現在讓我們回想上面對于橋的性質的描述：

如果一條邊是一個橋，那么它以下的子樹都無法通過別的邊與上面向連通。

這是不是很想我們講強連通分量里面的一句話：

我們假設一個節點與它的子樹形成了一個 SCC，那么它以及它的所有子樹都不會通過返祖邊與橫叉邊與其他點相連，而且一定會有返祖邊與這個根節點相連。

難道說，找 e-dcc 和找 SCC 有什么本質上的聯系嗎？

答案是有。根據橋的性質我們可以知道：一個橋以下的子樹的 low 是等于最頂上那個節點的 dfn 的（都分析了那么多遍了，這次應該自己看得懂了吧）。這跟 SCC 的求法幾乎一模一樣！

因此，我們就可以寫出代碼。

當然最后說一點：因為原圖是一個無向圖，所以并不存在前向邊和橫叉邊，因為這些邊都會通過一系列轉化變成返祖邊，因此 ins 數組就可以省去，因為所有的邊被換成返祖邊了之后，那些“祖先們”肯定只能和它下面的點形成 e-dcc，也就不存在會被提前“收服”的情況了。

核心代碼如下：

vector<int>v[N],edcc[N];
stack<int>st;
void e_dcc(int x,int fa)
{dfn[x]=low[x]=++ti;st.emplace(x);int sum=0;for(auto i:v[x]){if(i==fa){sum++;if(sum==1)//判重邊{continue;}low[x]=min(low[x],dfn[fa]);//否則更新}if(!dfn[i]){e_dcc(i,x);low[x]=min(low[x],low[i]);}else//不必再判{low[x]=min(low[x],dfn[i]);}}if(low[x]==dfn[x]){cnt++;while(1){int u=st.top();st.pop();edcc[cnt].emplace_back(u);if(u==x){break;}}}
}