[TOC]
# DFS Tree
將DFS走道的邊分成以下幾種:
1. 樹邊 (Tree edge):在 DFS 過程中,實際走進去的邊。樹邊會將原圖連接成一棵 DFS Tree。
2. 回邊 (Back edge):從 DFS Tree 的後代連向祖先的邊。
3. 交錯邊 (Cross edge):連接 DFS Tree 上兩個非祖孫關係的點的邊。
4. 前向邊 (Forward edge):不在 DFS Tree 上,但是從祖先連向後代的邊。
另外，無向圖只有樹邊和回邊。
# 無向圖
## 連通性
點連通度:對於一個連通圖定義它的點連通度為最少要移除幾個節點才可以使其不連通。
邊連通度:對於一個連通圖，定義它的邊連通度為最少要移除幾條邊才可以使其不連通。
若一張圖點連通度或邊連通度為$2$，則稱其為為點雙連通或邊雙連通。
一條邊被稱為橋(bridge)若某圖在移除它之後變得不連通。
一個節點被稱為割點(cut vertex)或關節點(articulationvertex)若某圖在移除它之後變得不連通。
## 邊雙連通分量
若把所有橋都拔掉，剩下的連通塊各會形成一個邊雙連通分量。
因此可以想像，在DFS Tree中，若把橋拔掉，則橋下面的節點都無法走到橋上面的節點，所以我們先嘗試找到所有的橋。
定義兩個函式:
* $\text{dep} [i]$ : 深度(depth)。
* $\text{low} [i]$ : 在不通過父邊的情況下，所能到達的最淺深度(lowpoint)。
依照定義，若`dep[i]==low[i]`，則$i$的父邊為橋(除了根節點)。
應該都會算深度吧
[Tree Distances I](https://cses.fi/problemset/task/1132)
```cpp=
void dfs(int pos){
for(int i:g[pos]){
if(!vis[i]){
vis[i]=1;
dep[i]=dep[pos]+1;
dfs(i);
}
}
}
```
接者利用dp的想法思考如何計算lowpoint:
若pos的某子節點i**還沒**被走過，則$\text{low} [pos]=\min(\text{low} [pos],\text{low} [i])$。
若pos的某子節點i**已經**被走過，則$\text{low} [pos]=\min(\text{low} [pos],\text{dep} [i])$。
稍微改一下程式碼:
```cpp=
void dfs(int pre,int pos){
for(int i:g[pos]){
if(i==pre) continue; //假想把父邊拿掉
if(!vis[i]){
vis[i]=1;
dep[i]=dep[pos]+1;
low[i]=dep[i];
dfs(pos,i);
low[pos]=min(low[pos],low[i]);
}
else{
low[pos]=min(low[pos],dep[i]);
}
}
if(dep[pos]!=0 && dep[pos]==low[pos]){
//邊(pre,pos)是橋
}
}
```
至此我們找到了所有的橋了，該如何找到每個點屬於哪個邊雙連通分量呢?
想像一下，如果把所有邊雙連通分量縮成一個點，則原圖會形成一個樹，所以對於每個節點，只要找到往上找到第一個橋就知道它屬於哪一個邊雙連通分量。
實際做法如下:
做DFS的時候不斷把節點推入stack，找到某個節點$p$的父邊是橋的時候就把stack的東西拿出來直到$p$，此時拿出的節點都會是$p$的子樹中的節點。
```cpp=
void dfs(int pre,int pos){
st.push(pos);
for(int i:g[pos]){
if(i==pre) continue; //假想把父邊拿掉
if(!vis[i]){
vis[i]=1;
dep[i]=dep[pos]+1;
low[i]=dep[i];
dfs(pos,i);
low[pos]=min(low[pos],low[i]);
}
else{
low[pos]=min(low[pos],dep[i]);
}
}
if(dep[pos]==low[pos]){
bcc.emplace_back();
while(st.top()!=pos){
idx[st.top()]=cnt;//每個節點屬於哪個分量
bcc[cnt].push_back(st.top());//每個分量有哪些節點
st.pop();
}
idx[st.top()]=cnt;
bcc[cnt].push_back(pos);
st.pop();
cnt++;
}
}
```
## 點雙連通分量
與邊雙連通分量類似，需要注意的是割點會被包含在很多點雙連通分量當中，有點像把點邊扮演的角色反轉，所以點雙連通分量一定要跟著找割點一起判斷，和邊雙連通的做法差不多。stack裡面可以放點或放邊，可以視需要改變實作方法。
我們沿用前面$\text{dep}$和$\text{low}$的定義，一條樹邊$(a, b)$（$a$是$b$的父親）若$low[b]=dep[a]$或$low[b]=dep[b]$，就代表a是個割點。有個特例是DFS tree的根，如果有超過一個子樹，那麼它是割點。
```cpp=
void dfs(int pre,int pos){
st.push(pos);
for(int i:g[pos]){
if(i==pre) continue;
if(!vis[i]){
vis[i]=1;
dep[i]=dep[pos]+1;
low[i]=dep[i];
dfs(pos,i);
low[pos]=min(low[pos],low[i]);
if(low[i]>=dep[pos]){
bcc.emplace_back();
while(st.top()!=i){
bcc[cnt].push_back(st.top());
st.pop();
}
bcc[cnt].push_back(st.top());
st.pop();
bcc[cnt].push_back(pos);//
cnt++;
}
}
else{
low[pos]=min(low[pos],dep[i]);
}
}
if(pre==-1){
st.pop();
if(g[pos].empty()){
bcc.emplace_back();
bcc[cnt].push_back(pos);
cnt++;
}
}
}
```
# 有向圖
## 連通性
* 弱連通(weakly connected):將所有有向邊替換為無向邊之後的無向圖是連通的。
* 單連通(unilaterally conncected):對於任意一對點$(u,v)$，存在從$u$到$v$**或**$v$到$u$的有向路徑。
* 強連通(strongly connected):對於任意一對點$(u,v)$，同時存在從$u$到$v$**和**$v$到$u$的有向路徑。
## 強連通分量
顧名思義，極大的強連通子圖。
一樣可以用無向圖的方法算，不過因為有cross edge，計算low時可能會跑到其他子樹，所以要開一個stack紀錄與當前的節點是否為同一個子樹。實作細節偏多，有興趣的可以看[這個](https://oi-wiki.org/graph/scc/#tarjan-%E7%AE%97%E6%B3%95)和[這個](https://www.youtube.com/watch?v=TyWtx7q2D7Y)，故在此介紹另一種演算法:
若把強連通分量各自縮成一個點，會形成一個有向無環圖(Directed Acyclic Graph,DAG)。
從這張圖可以發現，若我們從最右邊(也就是DAG拓樸排序的最尾端)的SCC開始DFS，那麼蒐集到的所有節點便是一個強連通分量(因為走不出去了)。
目標如下:
1. 排好某個順序，使得依照順序DFS的話走不出自己所在的分量。
2. 依照順序DFS，每一輪找到的節點自成一個強連通分量。
所以我們只要找到DAG的拓樸排序就可以知道該以什麼順序去DFS了。我們採用**後序走訪**，也就是說當某個節點走的到的地方都走過了，再紀錄該節點:
```cpp=
void dfs(int pos){
if(vis[pos]) return;
vis[pos]=1;
for(int i:g[pos]) dfs(i);
st.push(pos);
}
```
但是有一個問題，不同分量的拓樸排序有可能會重疊，如下圖:
stack(若後方為top)有可能是$[1,4,3,2]$(從2開始，先走1)或$[4,3,2,1]$(第一次從3開始，第二次從1開始)。但是仔細觀察後發現，stack最上面的節點一定屬於拓樸的頭的分量。換句話說，蒐集的部分，要是可以從拓樸的頭(而非尾)開始就好了……，但是會走出自己的分量，該怎麼解決?
靈光乍現!我們第二步可以在**反圖**上蒐集，這樣依照剛剛的觀察，就可以保證走不出自己的分量了，並且強連通分量取反之後依然會是強連通分量。不太懂的話可以看一下[模擬的影片](https://www.youtube.com/watch?v=Jb1XlDsr46o)，思考一下。
```cpp=
void dfs1(int pos){
if(vis[pos]) return;
vis[pos]=1;
for(int i:v[pos]) dfs1(i);
st.push(pos);
}
void dfs2(int pos){
if(vis[pos]) return;
vis[pos]=1;
idx[pos]=cnt;
for(int i:v2[pos]) dfs2(i);
}
```
## 2-SAT
有一些布林變數$X_1\, X_2\, \cdots \, X_n$，及一條式如:
$$
(a_1 \lor b_1)\land (a_2 \lor b_2)\land \cdots \land (a_m \lor b_m)
$$
其中$a_i$、$b_i$皆為某個$X_j$或它的取反$\lnot X_j$，為所有的$X$賦值使得上式為真。
觀察:
若$a_i$為False，$b_i$必為True；若$b_i$為False，$a_i$必為True。
我們可以為每個$X_i$和$\lnot X_i$建立一個節點，並對於所有的「若$a$為真，則$b$為真」連一條$a$到$b$的邊。
也就是說，對於所有括號內的兩個變數，建立一條$\lnot a_i$到$b_i$的邊和一條$\lnot b_i$到$a_i$的邊。
套用前面SCC的性質，同一個SCC的節點必全為真或全為假，所以我們可以進行縮點，將原圖縮為一張DAG，再對新的節點賦值就好。另外為了賦值時不會影響到剩下的節點，我們要從拓樸排序的尾開始。總結步驟如下:
1. 對於所有括號內的兩個變數，建立一條$\lnot a_i$到$b_i$的邊和一條$\lnot b_i$到$a_i$的邊。
2. 找每個節點屬於哪強連通分量。
3. 建立DAG。
4. 進行拓樸排序。
5. 從尾端開始放，將還不確定的SCC設為True，同時把該SCC中變數取not所在的SCC也賦值，以此類推。由於是由拓樸排序後面的開始做，因此不會發生解到一半產生矛盾的情形。
可以看下面Giant Pizza的code。
# 題目
## [【模板】点双连通分量](https://www.luogu.com.cn/problem/P8435)
:::spoiler 提示:
小心處理只有一個點的連通塊
:::
---
## [【模板】边双连通分量](https://www.luogu.com.cn/problem/P8436)
:::spoiler 提示:
有重邊，因此在`if(i==pre) continue`要改為「是不是走到上一個邊」，而不是「是不是走到上一個點」。
:::
---
## [One-Way Streets](https://oj.uz/problem/view/CEOI17_oneway)
---
## [Planets and Kingdoms](https://cses.fi/problemset/task/1683)
強連通分量模板
---
## [Strongly Connected Edges](https://cses.fi/problemset/task/2177)
:::spoiler 提示:
只要是原圖是邊雙連通的，就存在解。
:::
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
set<pair<int,int>> ans;
vector<set<int>> g;
vector<int> dep,low,vis;
void dfs(int pre,int pos){
for(int i:g[pos]){
if(i==pre||(ans.find({pos,i})!=ans.end()||ans.find({i,pos})!=ans.end())) continue;
if(!vis[i]){
vis[i]=1;
ans.insert({pos,i});
dep[i]=dep[pos]+1;
low[i]=dep[i];
dfs(pos,i);
low[pos]=min(low[pos],low[i]);
}
else{
ans.insert({pos,i});
low[pos]=min(low[pos],dep[i]);
}
}
}
int main(){
int n,m;
cin>>n>>m;
g.resize(n);
dep.resize(n);
low.resize(n);
vis.resize(n);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;
b--;
g[a].insert(b);
g[b].insert(a);
}
vis[0]=1;
dfs(0,0);
for(int i=0;i<n;i++){
if(!vis[i] || (i!=0&&low[i]==dep[i])){
cout<<"IMPOSSIBLE"<<endl;
return 0;
}
}
for(auto i:ans){
cout<<i.first+1<<" "<<i.second+1<<endl;
}
return 0;
}
```
:::
---
## [Giant Pizza](https://cses.fi/problemset/task/1684/)
2-SAT模板
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> g,gr,dag,SCC(1);
vector<int> vis,idx,dic,dagdic;
stack<int> st;
queue<int> qu;
int cnt=0;
void dfs1(int pos){
if(vis[pos]) return;
vis[pos]=1;
for(int i:g[pos]) dfs1(i);
st.push(pos);
}
void dfs2(int pos){
if(vis[pos]) return;
vis[pos]=1;
idx[pos]=cnt;
SCC[cnt].push_back(pos);
for(int i:gr[pos]) dfs2(i);
}
void dfs3(int pos){
if(vis[pos]) return;
vis[pos]=1;
for(int i:dag[pos]) dfs3(i);
qu.push(pos);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin>>n>>m;
g.resize(2*m);//-+
gr.resize(2*m);
idx.resize(2*m);
dic.resize(m);
vis.resize(2*m);
for(int i=0;i<n;i++){
string a,b;
int c,d;
cin>>a>>c>>b>>d;
c--;
d--;
if(a=="+"&&b=="+"){
g[c].push_back(d+m);
g[d].push_back(c+m);
gr[c+m].push_back(d);
gr[d+m].push_back(c);
}
else if(a=="+"&&b=="-"){
g[c].push_back(d);
g[d+m].push_back(c+m);
gr[c+m].push_back(d+m);
gr[d].push_back(c);
}
else if(a=="-"&&b=="-"){
g[c+m].push_back(d);
g[d+m].push_back(c);
gr[c].push_back(d+m);
gr[d].push_back(c+m);
}
else if(a=="-"&&b=="+"){
g[c+m].push_back(d+m);
g[d].push_back(c);
gr[c].push_back(d);
gr[d+m].push_back(c+m);
}
}
for(int i=0;i<2*m;i++){
dfs1(i);
}
vis.clear();
vis.resize(2*m,0);
while(!st.empty()){
if(!vis[st.top()]){
cnt++;
SCC.emplace_back();
}
dfs2(st.top());
st.pop();
}
for(int i=0;i<m;i++){
if(idx[i]==idx[i+m]){
cout<<"IMPOSSIBLE"<<endl;
return 0;
}
}
dag.resize(cnt+1);
dagdic.resize(cnt+1,-1);
for(int i=0;i<2*m;i++){
for(int j:g[i]){
if(idx[i]!=idx[j]){
dag[idx[i]].push_back(idx[j]);
}
}
}
vis.clear();
vis.resize(cnt+1,0);
for(int i=1;i<=cnt;i++){
dfs3(i);
}
while(!qu.empty()){
int scc=qu.front();
qu.pop();
if(dagdic[scc]==-1){
dagdic[scc]=1;
}
if(dagdic[scc]==1){
for(int i:SCC[scc]){
if(i>=m){
dic[i-m]=1;
dagdic[idx[i-m]]=0;
}
else{
dic[i]=0;
dagdic[idx[i+m]]=0;
}
}
}
else if(dagdic[scc]==0){
for(int i:SCC[scc]){
if(i>=m){
dic[i-m]=0;
dagdic[idx[i-m]]=1;
}
else{
dic[i]=1;
dagdic[idx[i+m]]=1;
}
}
}
}
for(int i:dic){
if(i==0) cout<<"- ";
else cout<<"+ ";
}
cout<<endl;
return 0;
}
```
:::
---
## [Acyclic Graph Edges](https://cses.fi/problemset/task/1756)
:::spoiler 提示:
這題的作法其實和本單元完全沒有任何關係而且超簡單。放進來只是因為題敘很像。
:::
---
## [E. Ralph and Mushrooms](https://codeforces.com/contest/894/problem/E)
:::spoiler 提示:
強連通分量+dp
:::
[題解](https://codeforces.com/blog/entry/55884)
---
## [D. Catowice City](https://codeforces.com/contest/1239/problem/D)
[題解](https://codeforces.com/blog/entry/70720)
---
## [Bike paths](https://szkopul.edu.pl/problemset/problem/aKKSmtjWTtDOEHDqnmQ3-eAA/site/?key=statement)
[題解](https://usaco.guide/problems/poi-2018bike-paths/solution)
---
## [受欢迎的牛](https://www.luogu.com.cn/problem/P2341)
:::spoiler 提示:
考慮強連通分量縮點。
另外這題其實可以暴力+剪枝做。
:::
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,num=0;
vector<vector<int>> g,gr;
vector<int> vis,idx;
stack<int> st;
void dfs1(int pos){
if(vis[pos]) return;
vis[pos]=1;
for(int i:g[pos]) dfs1(i);
st.push(pos);
}
void dfs2(int pos){
if(vis[pos]) return;
vis[pos]=1;
for(int i:gr[pos]) dfs2(i);
idx[pos]=num;
}
signed main(){
cin>>n>>m;
g.resize(n);
gr.resize(n);
vis.resize(n);
idx.resize(n);
while(m--){
int a,b;
cin>>a>>b;
a--;
b--;
g[a].push_back(b);
gr[b].push_back(a);
}
for(int i=0;i<n;i++){
if(!vis[i]) dfs1(i);
}
if(st.size()!=n){
cout<<0<<endl;
return 0;
}
vis.clear();
vis.resize(n,0);
while(!st.empty()){
int t=st.top();
st.pop();
if(vis[t]) continue;
dfs2(t);
num++;
}
vector<int> outcnt(num);
for(int i=0;i<n;i++){
for(int j:g[i]){
if(idx[i]!=idx[j]){
outcnt[idx[i]]++;
}
}
}
int cnt=0,ans;
for(int i=0;i<num;i++){
if(outcnt[i]==0){
cnt++;
ans=i;
}
}
if(cnt>1){
cout<<0<<endl;
return 0;
}
int fnans=0;
for(int i=0;i<n;i++){
if(idx[i]==ans) fnans++;
}
cout<<fnans<<endl;
return 0;
}
```
:::
---
## [校园网Network of Schools](https://www.luogu.com.cn/problem/P2746)
---
## 待補
# reference
[維基百科](https://zh.wikipedia.org/zh-tw/%E8%BF%9E%E9%80%9A%E5%9B%BE)
[臺南一中資訊社2022暑訓](https://www.youtube.com/watch?v=5zTi0x8ZRLs)
[台師大演算法筆記](https://web.ntnu.edu.tw/~algo/ConnectedComponent.html)
[USACO guide](https://usaco.guide/adv/SCC?lang=cpp)
2016建中資培講義
2019板中資培講義
2023 IOI Camp講義
2023 ION Camp講義
# 梗圖
Sign in with Wallet
Connect another wallet