算法学习笔记（Tarjan）

本文介绍$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$边的情况？）