网站推广公司运营模式,南京市招办南京网站设计,房产网查询,怎样看一个网站的信息吗TARJAN复习 求强连通分量、割点、桥 文章目录 TARJAN复习 求强连通分量、割点、桥强连通分量缩点桥割点 感觉之前写的不好#xff0c;
再水一篇博客 强连通分量 “有向图强连通分量#xff1a;在有向图G中#xff0c;如果两个顶点vi,vj间#xff08;vivj#xff09;有…TARJAN复习 求强连通分量、割点、桥 文章目录 TARJAN复习 求强连通分量、割点、桥强连通分量缩点桥割点 感觉之前写的不好
再水一篇博客 强连通分量 “有向图强连通分量在有向图G中如果两个顶点vi,vj间vivj有一条从vi到vj的有向路径同时还有一条从vj到vi的有向路径则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通称G是一个强连通图。有向图的极大强连通子图称为强连通分量(strongly connected components)。 ----百度 像上面的这个图就有三个强连通分量
1-2-3、4、5
设 d f n i dfn_i dfni 记录到达点 i i i 的时间戳
设 l o w i low_i lowi 表示 i i i 能到达的所有点的时间戳
如果 l o w i d f n i low_i dfn_i lowidfni 就意味着 i i i 和 i i i 下面的点能够组成一个强连通分量因为 i i i 下面已经没有边可以往 i i i 祖先方向上走了
实现的时候就用一个栈维护一下那个顺序就好了
缩点
P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
看一下这个题
对于一个强连通分量来说
我们可以把它缩成一个点并把这个点的权值设成这个强连通分量里面所有点的权值和。
然后再做 d p dp dp 就好了
#includebits/stdc.h
#define LL long long
#define fu(x , y , z) for(int x y ; x z ; x )
using namespace std;
stackint stk;
queueint que;
const int N 1e4 5 , M 1e5 5;
LL ans , f[N] , w[N];
int hd[N] , hd2[N] , num , cnt2 , cnt , p[N] , dfn[N] , low[N] , a[N] , n , ru[N] , m , b[N] , num1;
struct E {int nt , to , fr;
}e[M 1];
struct EE {int nt , to;
}e2[M 1];
int read () {int val 0 , fu 1;char ch getchar ();while (ch 0 || ch 9) {if (ch -) fu -1;ch getchar ();}while (ch 0 ch 9) {val val * 10 (ch - 0);ch getchar ();}return val * fu;
}
void add (int x , int y) {e[cnt].to y , e[cnt].nt hd[x] , e[cnt].fr x , hd[x] cnt;
}
void dfs (int x , int fa) {dfn[x] low[x] num;stk.push(x);int y;for (int i hd[x] ; i ; i e[i].nt) {y e[i].to;if (!dfn[y]) {dfs (y , x);low[x] min (low[x] , low[y]);}else if (!p[y])low[x] min (low[x] , dfn[y]);}if (low[x] dfn[x]) {y 0;num1 ;while (y ! x !stk.empty()) {y stk.top();stk.pop();p[y] num1;w[num1] a[y];}f[num1] w[num1]; }
}
void add2 (int x , int y) { e2[cnt2].to y , e2[cnt2].nt hd2[x] , hd2[x] cnt2; }
void build () {int fa1 , fa2 , x , y;fu(i , 1 , cnt) {x p[e[i].fr] , y p[e[i].to];if (x y) continue;add2 (x , y);ru[y] ;}
}
void tuo () {fu(i , 1 , num1)if (!ru[i])que.push(i);int x , y;while (!que.empty()) {x que.front();que.pop();for (int i hd2[x] ; i ; i e2[i].nt) {y e2[i].to;ru[y] --;if (!ru[y])que.push(y);f[y] max (f[y] , f[x] w[y]);}}
}
int main () {int u , v;n read () , m read ();fu(i , 1 , n) a[i] read ();fu(i , 1 , m) {u read () , v read ();add (u , v);}fu(i , 1 , n)if (!dfn[i])dfs (i , 0);build ();tuo ();fu(i , 1 , num)ans max (ans , f[i]);printf (%lld , ans);return 0;
}桥 在一个图中如果存在一条边把它删掉使得整个图被分出来两个互相不连通的图那么这条边就是桥 d f n dfn dfn 跟求强连通分量的一样 l o w i low_i lowi 表示 i i i 能够到达的最先被访问过的点**不包括 i i i 的父亲**
设 u , v u , v u,v v v v 是 u u u 的儿子。
如果 l o w v d f n u low_v dfn_u lowvdfnu 就意味着 v v v 不能到达 u u u 之前的点了除非经过 u → v u\to v u→v 这条边所以这条边就是桥
P1656 炸铁路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include bits/stdc.h
#define fu(x , y , z) for(int x y ; x z ; x )
using namespace std;
const int N 155 , M 5005;
int n , m , hd[N] , cnt 1 , dfn[N] , low[N] , num , ans1;
struct E {int to , nt;
} e[M 1];
struct ANS {int u , v;
} ans[M];
bool cmp (ANS x , ANS y) { return x.u ! y.u ? x.u y.u : x.v y.v; }
void add (int x , int y) { e[cnt].to y , e[cnt].nt hd[x] , hd[x] cnt; }
void dfs (int x , int fa) {dfn[x] low[x] num;int y;for (int i hd[x] ; i ; i e[i].nt) {y e[i].to;if (y fa) continue;if (!dfn[y]) {dfs (y , x);if (dfn[x] low[y]) {ans[ans1].u min (x , y);ans[ans1].v max (x , y);}low[x] min (low[x] , low[y]);}elselow[x] min (low[x] , dfn[y]);}
}
int main () {int u , v;scanf (%d%d , n , m);fu (i , 1 , m) {scanf (%d%d , u , v);add (u , v) , add (v , u);}fu (i , 1 , n) {if (!dfn[i]) dfs (i , 0);}sort (ans 1 , ans ans1 1 , cmp);fu (i , 1 , ans1) printf (%d %d\n , ans[i].u , ans[i].v);return 0;
}割点 在一个图中如果能够删掉一个点和连接这个点的所有边使得这个图分成两个不相连的连通块那么这个点就是割点 跟桥差不多。
因为当你找到一条桥连接 u , v u , v u,v 且 u u u 是 v v v 的父亲时 u u u 一定是割点因为 v v v 连不出去了
还有一种情况就是 u u u 是根且 u u u 有超过一个不同的子树那么 u u u 也是割点。
P3388 【模板】割点割顶 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include bits/stdc.h
#define fu(x , y , z) for(int x y ; x z ; x )
using namespace std;
const int N 2e4 5 , M 2e5 5;
int n , m , cnt , hd[N] , dfn[N] , low[N] , num , flg[N] , ans;
struct E {int to , nt;
} e[M 1];
void add (int x , int y) { e[cnt].to y , e[cnt].nt hd[x] , hd[x] cnt; }
void dfs (int x , int fa) {dfn[x] low[x] num;int y , sz 0;for (int i hd[x] ; i ; i e[i].nt) {y e[i].to;if (!dfn[y]) {dfs (y , x);if (dfn[x] low[y] fa)flg[x] 1;low[x] min (low[x] , low[y]);sz ;}elselow[x] min (low[x] , dfn[y]);}if (!fa sz 2)flg[x] 1;if (flg[x]) ans ;
}
int main () {int u , v;scanf (%d%d , n , m);fu (i , 1 , m) {scanf (%d%d , u , v);add (u , v) , add (v , u);}fu (i , 1 , n) {if (!dfn[i]) dfs (i , 0);}printf (%d\n , ans);fu (i , 1 , n)if (flg[i])printf (%d , i);return 0;
}
