本文介绍 T a r j a n Tarjan Tarjan求强联通分量、找割点和割边、找环。
Tarjan求强联通分量
例题:【模板】有向图缩点
题目描述
给定一个 n n n点 m m m边的有向图(保证不存在重边与自环,但不保证连通),请你求出其中所有“大小大于 1 1 1”的强联通分量的大小,如果不存在则输出 − 1 −1 −1。
将所有强联通分量大小按从小到大顺序输出。
输入描述
第一行两个整数 n , m n,m n,m。 ( 1 ≤ n , m ≤ 2 × 1 0 5 ) (1 \leq n,m \leq 2 \times 10^5) (1≤n,m≤2×105)
接下来 m m m行,每行一条边 ( x , y ) (x,y) (x,y),表示存在一条由点 x x x到点 y y y的边。 ( 1 ≤ x , y ≤ n ) (1≤x,y≤n) (1≤x,y≤n)
输出描述
一行从小到大输出所有“大小大于 1 1 1”的强联通分量的大小,若不存在则输出 − 1 −1 −1。
输入样例1
4 4
1 2
2 3
3 1
1 4
输出样例1
3
强连通:在有向图 G G G中,如果两个点 u u u和 v v v是互相可达的,即从 u u u出发可以到达 v v v,从 v v v出发可以到达 u u u,则称 u u u和 v v v是强连通的。如果 G G G中任意两个点都是互相可达的,称 G G G是强连通图。
强连通分量(SCC):如果一个有向图 G G G不是强连通图,那么可以把它分成多个子图,其中每个子图的内部是强连通的,而且这些子图已经扩展到最大,不能与子图外的任意点强连通,称这样的一个“极大强连通”子图是 G G G的一个强连通分量。
接下来说明一个定理: S C C SCC SCC,从其中任意一个点出发,都至少有一条路径能绕回到自己。
明白这点之后,解释一下 T a r j a n Tarjan Tarjan求强连通分量的流程。
首先对于每一个节点,都有两个量: d f n dfn dfn和 l o w low low, d f n dfn dfn表示该节点的 d f s dfs dfs序, l o w low low则表示该节点能返回到的最远祖先(对图跑 d f s dfs dfs生成搜索树,树上节点有祖先),初始时 l o w low low就等于自己的 d f s dfs dfs序,在之后更新的时候,有两种情况可以更新 l o w low low的值。一种是一个节点有一条有向边指向自己在搜索树上的祖先时,比较自己的 l o w low low和被访问到的祖先的 d f n dfn dfn,将自己的 l o w low low更新为两者中的最小值。还有一种情况就是 d f s dfs dfs回溯时,比较自己的 l o w low low和儿子的 l o w low low,将自己的 l o w low low更新为两者中的较小值。更新完回来之后,回到 d f n = l o w dfn = low dfn=low的点,作为强连通分量的根。将刚刚修改过 l o w low low值的点收拢,作为一个强连通分量。
特殊的,如果一个点有一条有向边指向了一个强连通分量,那么我们不应该去更新它的 l o w low low。
为了区别这种情况,我们会使用栈来分离不同的 S C C SCC SCC,每访问一个点就将点丢入栈中,而每找出一个 S C C SCC SCC,则将这个 S C C SCC SCC中的所有点从栈中弹出。之后有边指向这个 S C C SCC SCC则不再理会(指向的点不在栈中说明已经属于一个 S C C SCC SCC)。
时间复杂度为: O ( n + m ) O(n + m) 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 n n点 m m m边的无向图(无重边与自环),请求出图中所有割点和割边的数量。
输入描述
第一行两个整数 n , m n,m n,m。 ( 1 ≤ n , m ≤ 2 × 1 0 5 ) (1 \leq n,m \leq 2 \times 10^5) (1≤n,m≤2×105)
接下来 m m m行,每行两个整数 x , y x,y x,y表示一条 x x x与 y y y之间的双向边。 ( 1 ≤ x , y ≤ n ) (1 \leq x,y \leq n) (1≤x,y≤n)。
输出描述
一行两个整数,表示割点和割边的数量。
输入样例1
4 4
1 2
3 2
2 4
1 3
输出样例1
1 1
解释
割点为 2 2 2,割边为 2 − 4 2−4 2−4。
割点和割边:无向图中所有能互通的点组成了一个“连通分量”。在一个连通分量中有一些关键的的点,如果删除它们,会把这个连通分量断开分为两个或更多,这种点称为割点。同样的,如果在一个连通分量中删除一条边,把这个连通分量分成了两个,这条边称为割边。
对于一个点:分两种情况,一是不作为搜索树的根的节点,只要在由这个节点的儿子中,有一个节点不连通到该节点的祖先( l o w [ y ] ≥ d f n [ x ] low[y] \geq dfn[x] low[y]≥dfn[x]),那么这个节点是割点(由该节点作为分界线,分割了它的儿子做根的子树和它的父亲)。二是作为搜索树的根的节点,需要两个儿子不连通到该节点( l o w [ y ] ≥ d f n [ x ] low[y] \geq dfn[x] low[y]≥dfn[x]),那么这个节点是割点(删除这个根,两棵子树就被分离开来了)。
而对于一条边,只要后边的点回不到前边的点( l o w [ y ] ≥ d f n [ x ] low[y] \geq dfn[x] low[y]≥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 n点 n n n边的无向连通图(不含重边与自环),请你求出图中环的大小。
可以证明图中存在且仅存在一个环。
输入描述
第一行一个整数表示测试样例数量 T T T。 ( 1 ≤ T ≤ 1000 ) (1 \leq T \leq 1000) (1≤T≤1000)
对于每组测试样例,第一行一个整数 n n n。 ( 1 ≤ n ≤ 2 × 1 0 5 ) (1 \leq n \leq 2 \times 10^5) (1≤n≤2×105)
接下来 n n n行,每行一条无向边 u , v u,v u,v。 ( 1 ≤ u , v ≤ n ) (1 \leq u,v \leq n) (1≤u,v≤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点 n n n边,一定存在且仅存在一个环(一棵树 n − 1 n - 1 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;
}
( T a r j a n Tarjan Tarjan找环应该只使用于 n n n点 n n n边的情况?)