专做国际时事评论网站,艺术字体在线生成器英文,建设银行流水网站,房屋装修设计培训学校本文介绍 T a r j a n Tarjan Tarjan求强联通分量、找割点和割边、找环。
Tarjan求强联通分量
例题#xff1a;【模板】有向图缩点
题目描述
给定一个 n n n点 m m m边的有向图#xff08;保证不存在重边与自环#xff0c;但不保证连通#xff09;#xff0c;请你求出…本文介绍 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 dfnlow的点作为强连通分量的根。将刚刚修改过 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(nm)
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e5 9, T 20;vectorint g[N];int dfn[N], low[N], stk[N], top, idx;
int tot, cnt[N];
bitsetN 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);vectorint 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;vectorint 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]);}
}setpairint, 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;vectorint g[N];int dfn[N], low[N], idx, ans;
int stk[N], top;
bitsetN 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边的情况
