TARJAN复习 求强连通分量、割点、桥
文章目录
- TARJAN复习 求强连通分量、割点、桥
-
- 强连通分量
- 缩点
- 桥
- 割点
感觉之前写的不好,
再水一篇博客
强连通分量
“有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从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
lowi==dfni 就意味着
i
i
i 和
i
i
i 下面的点能够组成一个强连通分量,因为
i
i
i 下面已经没有边可以往
i
i
i 祖先方向上走了
实现的时候就用一个栈维护一下那个顺序就好了
缩点
P3387 【模板】缩点 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
看一下这个题
对于一个强连通分量来说
我们可以把它缩成一个点,并把这个点的权值设成这个强连通分量里面所有点的权值和。
然后再做
d
p
dp
dp 就好了
#include
#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
lowv>dfnu 就意味着
v
v
v 不能到达
u
u
u 之前的点了,除非经过
u
→
v
uto v
u→v 这条边,所以这条边就是桥
P1656 炸铁路 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include
#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]);
}
else
low[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 %dn" , 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
#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 ++;
}
else
low[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 ("%dn" , ans);
fu (i , 1 , n)
if (flg[i])
printf ("%d " , i);
return 0;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net