本文介紹$Tarjan$求強聯通分量、找割點和割邊、找環。

Tarjan求強聯通分量

例題：【模板】有向圖縮點

題目描述

給定一個$n$點$m$邊的有向圖（保證不存在重邊與自環，但不保證連通），請你求出其中所有“大小大于$1$”的強聯通分量的大小，如果不存在則輸出$?1$。

將所有強聯通分量大小按從小到大順序輸出。

輸入描述

第一行兩個整數$n,m$。$(1\le n,m\le 2\times 10^5)$

接下來$m$行，每行一條邊$(x,y)$，表示存在一條由點$x$到點$y$的邊。$(1\le x,y\le n)$

輸出描述

一行從小到大輸出所有“大小大于$1$”的強聯通分量的大小，若不存在則輸出$?1$。

輸入樣例1

4 4
1 2
2 3
3 1
1 4

輸出樣例1

3

---

強連通：在有向圖$G$中，如果兩個點$u$和$v$是互相可達的，即從$u$出發可以到達$v$，從$v$出發可以到達$u$，則稱$u$和$v$是強連通的。如果$G$中任意兩個點都是互相可達的，稱$G$是強連通圖。

強連通分量（SCC）：如果一個有向圖$G$不是強連通圖，那么可以把它分成多個子圖，其中每個子圖的內部是強連通的，而且這些子圖已經擴展到最大，不能與子圖外的任意點強連通，稱這樣的一個“極大強連通”子圖是$G$的一個強連通分量。

接下來說明一個定理：$SCC$，從其中任意一個點出發，都至少有一條路徑能繞回到自己。

明白這點之后，解釋一下$Tarjan$求強連通分量的流程。

首先對于每一個節點，都有兩個量：$dfn$和$low$，$dfn$表示該節點的$dfs$序，$low$則表示該節點能返回到的最遠祖先（對圖跑$dfs$生成搜索樹，樹上節點有祖先）,初始時$low$就等于自己的$dfs$序，在之后更新的時候，有兩種情況可以更新$low$的值。一種是一個節點有一條有向邊指向自己在搜索樹上的祖先時，比較自己的$low$和被訪問到的祖先的$dfn$，將自己的$low$更新為兩者中的最小值。還有一種情況就是$dfs$回溯時，比較自己的$low$和兒子的$low$，將自己的$low$更新為兩者中的較小值。更新完回來之后，回到$dfn=low$的點，作為強連通分量的根。將剛剛修改過$low$值的點收攏，作為一個強連通分量。

特殊的，如果一個點有一條有向邊指向了一個強連通分量，那么我們不應該去更新它的$low$。

為了區別這種情況，我們會使用棧來分離不同的$SCC$，每訪問一個點就將點丟入棧中，而每找出一個$SCC$，則將這個$SCC$中的所有點從棧中彈出。之后有邊指向這個$SCC$則不再理會（指向的點不在棧中說明已經屬于一個$SCC$）。

時間復雜度為：$O(n+m)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 9, T = 20;vector<int> g[N];int dfn[N], low[N], stk[N], top, idx;
int tot, cnt[N];
bitset<N> ins;//tarjan的本質是dfs
void tarjan(int x)
{//1.初始化dfn和lowdfn[x] = low[x] = ++ idx;//2.入棧并標記stk[++ top] = x;ins[x] = true;//3.遍歷所有兒子for(const auto &y : g[x]){//判斷是否是回點if(!dfn[y]){tarjan(y);low[x] = min(low[x], low[y]);}else if(ins[y]) low[x] = min(low[x], dfn[y]);}//4.收攏if(low[x] == dfn[x]){//新開一個顏色tot ++;while(stk[top + 1] != x){//計數cnt[tot] ++;//取消標記ins[stk[top --]] = false;}}
}void solve()
{int n, m;cin >> n >> m;for(int i = 1;i <= m; ++ i){int x, y;cin >> x >> y;g[x].push_back(y);}for(int i = 1;i <= n; ++ i)if(!dfn[i])tarjan(i);vector<int> v;for(int i = 1;i <= tot; ++ i)if(cnt[i] > 1)v.push_back(cnt[i]);if(v.size()){sort(v.begin(), v.end());for(const auto &i : v)cout << i << ' ';}else cout << -1 << '\n';
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;while(_ --)solve();return 0;
}

Tarjan求割點和割邊

例題：【模板】無向圖求割點、割邊

題目描述

給一個$n$點$m$邊的無向圖（無重邊與自環），請求出圖中所有割點和割邊的數量。

輸入描述

第一行兩個整數$n,m$。$(1\le n,m\le 2\times 10^5)$

接下來$m$行，每行兩個整數$x,y$表示一條$x$與$y$之間的雙向邊。$(1\le x,y\le n)$。

輸出描述

一行兩個整數，表示割點和割邊的數量。

輸入樣例1

4 4
1 2
3 2
2 4
1 3

輸出樣例1

1 1

解釋

割點為$2$，割邊為$2?4$。

---

割點和割邊：無向圖中所有能互通的點組成了一個“連通分量”。在一個連通分量中有一些關鍵的的點，如果刪除它們，會把這個連通分量斷開分為兩個或更多，這種點稱為割點。同樣的，如果在一個連通分量中刪除一條邊，把這個連通分量分成了兩個，這條邊稱為割邊。

對于一個點：分兩種情況，一是不作為搜索樹的根的節點，只要在由這個節點的兒子中，有一個節點不連通到該節點的祖先（$low[y]\ge dfn[x]$），那么這個節點是割點（由該節點作為分界線，分割了它的兒子做根的子樹和它的父親）。二是作為搜索樹的根的節點，需要兩個兒子不連通到該節點（$low[y]\ge dfn[x]$），那么這個節點是割點（刪除這個根，兩棵子樹就被分離開來了）。

而對于一條邊，只要后邊的點回不到前邊的點（$low[y]\ge dfn[x]$），那么這個點就是割邊。

那么計算割點割邊只需要看是否滿足上述條件就行。

#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 9;vector<int> g[N];int dfn[N], low[N], idx, cut, es;void tarjan1(int x, int fa)
{dfn[x] = low[x] = ++ idx;int child = 0;for(const auto &y: g[x]){//1.不走父親if(y == fa)continue;//2.判斷是否是搜索樹的兒子if(!dfn[y]){tarjan1(y, x);low[x] = min(low[x], low[y]);child += (low[y] >= dfn[x]);}else low[x] = min(low[x], dfn[y]);}if((!fa && child >= 2) || (fa && child >= 1))cut ++;
}void tarjan2(int x, int fa)
{dfn[x] = low[x] = ++ idx;for(const auto &y : g[x]){if(y == fa)continue;//如果y沒被走過，就往下走if(!dfn[y]){//此時y是x在搜索樹中的兒子tarjan2(y, x);low[x] = min(low[x], low[y]);//如果y回不到自身以及父親樹上if(low[y] > dfn[x])es ++;}else low[x] = min(low[x], dfn[y]);}
}set<pair<int, int> > st;void solve()
{int n, m;cin >> n >> m;for(int i = 1;i <= m; ++ i){int x, y;cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}for(int i = 1;i <= n; ++ i)if(!dfn[i])tarjan1(i, 0);for(int i = 1;i <= n; ++ i)dfn[i] = low[i] = 0;idx = 0;for(int i = 1;i <= n; ++ i)if(!dfn[i])tarjan2(i, 0);cout << cut << ' ' << es << '\n';
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1;while(_ --)solve();return 0;
}

Tarjan找環

例題：【模板】Tarjan找環

題目描述

給定一個$n$點$n$邊的無向連通圖（不含重邊與自環），請你求出圖中環的大小。

可以證明圖中存在且僅存在一個環。

輸入描述

第一行一個整數表示測試樣例數量$T$。$(1\le T\le 1000)$

對于每組測試樣例，第一行一個整數$n$。$(1\le n\le 2\times 10^5)$

接下來$n$行，每行一條無向邊$u,v$。$(1\le u,v\le n)$

輸出描述

對于每組測試樣例，輸出一個整數表示環的大小。

輸入樣例1

2
5
1 2
1 3
2 3
3 4
4 5
4
1 2
2 3
3 4
1 4

輸出樣例1

3
4

---

對于找環，找出一個強連通分量就是環。因為$n$點$n$邊，一定存在且僅存在一個環（一棵樹$n?1$條邊，多連一條邊必定生成一個環）。于是只要在找強連通分量的代碼上稍加修改就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 9;vector<int> g[N];int dfn[N], low[N], idx, ans;
int stk[N], top;
bitset<N> ins;void tarjan(int x, int fa)
{dfn[x] = low[x] = ++ idx;stk[++ top] = x;ins[x] = true;for(const auto &y : g[x]){if(y == fa)continue;if(!dfn[y]){tarjan(y, x);low[x] = min(low[x], low[y]);}else if(ins[x])low[x] = min(low[x], dfn[y]);}if(low[x] == dfn[x]){int cnt = 0;while(stk[top + 1] != x){cnt ++;ins[stk[top --]] = false;}if(cnt > 1){ans = cnt;return;}}}void solve()
{int n;cin >> n;for(int i = 1;i <= n; ++ i){g[i].clear();stk[i] = dfn[i] = low[i] = 0;ins[i] = false;}stk[n + 1] = 0;ans = idx = top = 0;for(int i = 1;i <= n; ++ i){int x, y;cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}tarjan(1, 0);cout << ans << '\n';
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while(_ --)solve();return 0;
}

（$Tarjan$找環應該只使用于$n$點$n$邊的情況？）