首先我们需要搞懂图论中的一些基础概念
完全图: 假设一个图有 n n n 个顶点, 并且每两个点之间都有边就叫完全图
连通图(多指无向图): 对于两个点, u , v , u,v, u,v, 如果 u , v u,v u,v 之间有通路,则称 u , v u,v u,v 两点连通, 如果图中任意两个点都连通, 则称这个图为连通图
连通分量: 连通分量中任意两点 u , v , u,v, u,v, 两两之间必定能互相到达, u − > v , v − > u . u->v, v->u. u−>v,v−>u. (当然一个点也是连通分量)
强连通分量: 极大的连通分量,对于连通分量内部的任意两个点 u , v , u, v, u,v,, 既存在 u u u 到 v v v 的路径, 又存在 v v v 到 u u u的路径,并且如果再加入其它点和边就不再连通的,
tarjan算法求强连通分量
了解 t a r j a n tarjan tarjan 算法之前你必须了解一个概念, 时间戳
时间戳: 根据深度优先搜索的顺序给节点标号
有了时间戳后我们就可以引入两个概念:
d
f
n
[
u
]
dfn[u]
dfn[u]: 节点
u
u
u 所对应的时间戳
l
o
w
[
u
]
low[u]
low[u]: 节点
u
u
u 所能够到达的时间戳的最小值
如果 d f n [ u ] = = l o w [ u ] dfn[u] == low[u] dfn[u]==low[u] ⟺ iff ⟺ u u u 节点是所在强连通分量的最高点
判断一个点是否在某个强连通分量中 ⟺ iff ⟺ 该点是否能走到该强连通分量的最高点
tarjan 算法求强连通分量的步骤
- 缩点建图求拓扑序(递推)
1.缩点
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp; //分配编号
s.push(u), is_stack[u] = true; //入栈, 标记为在栈中
for(int i = h[u]; ~i; i = ne[i]) //遍历每条邻边
{
int j = e[i];
if(!dfn[j]) //如果这个点没有被搜索过
{
tarjan(j); //搜到底
low[u] = std :: min(low[u], low[j]); //用j更新u
}
else if(is_stack[j]) low[u] = std :: min(low[u], dfn[j]);
//如果这个点没被搜到过, 并且在栈中, 说明存在横叉边
}
if(dfn[u] == low[u]) //u点是所在强连通分量的最高点
{
int y;
scc_cnt ++; //强联通分量数量++
do
{
y = s.top(); //取出栈顶
s.pop();
size[scc_cnt] ++; //该连通分量中点的数量++
id[y] = scc_cnt; //分配编号
is_stack[y] = false; //标记为不在栈中
}while(y != u);
}
}
2.建图
for(int i = 1; i <= n; i ++ )
for(int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if(a != b) add(hs,a, b);//hs为新图的头结点
}
3.求拓扑序
for(int i = scc_cnt; i; i -- )
因为 t a r j a n tarjan tarjan 算法最后求出来的就是逆拓扑序, 所以不用再进行拓扑排序了
无向图的双连通分量
1.边的双连通分量
e
−
d
c
c
e-dcc
e−dcc 极大的不包含桥的连通块
2.点的双连通分量
v
−
d
c
c
v-dcc
v−dcc 极大的不包含割点的连通块
首先要知道桥是什么?
桥 就是去掉这条边后, 能使连通块数量增加的边(或者说使得这个图不连通)
割点 就是去掉这个点和它所关联的边,能使得连通块数量增加的点(或者说使得这个图不连通)
点双连通分量的特殊性质
除了只包含两个点的点双连通分量外, 其他点双连通分量都满足一个性质:
任
意
两
点
间
都
存
在
不
相
交
的
两
条
路
径
任意两点间都存在不相交的两条路径
任意两点间都存在不相交的两条路径
任何一个割点都存在于两个点双连通分量中
因为删去割点后, 图就不连通了, 所以割点连接的一定是不相同的两个点双连通分量
任意一个非割点都只存在于一个点双连通分量中
节点 1 , 6 1,6 1,6 是割点, 右边深色的是四个边双连通分量,可以看出每个割点都位于两个边双连通分量中
t a r j a n tarjan tarjan 求割点
割点的定义是删去这个点后图不连通, 那么肯定存在一些点,在不经过割点的情况下, 无法到达割点的祖先,所以我们可以通过这个性质去寻找割点
有割点
⟺
iff
⟺
l
o
w
[
y
]
≥
d
f
n
[
x
]
low[y] ≥ dfn[x]
low[y]≥dfn[x]
这是什么意思呢? 就是说节点
y
y
y 能够到达的最高点的时间戳比
x
x
x 的时间戳要大, 说明 节点
y
y
y无法到达 节点
x
x
x 的祖先, 所以如果删除节点
x
x
x, 就不连通了
这里存在两种情况:
- 如果
x
x
x 不是根节点, 那么只要
l
o
w
[
y
]
≥
d
f
n
[
x
]
low[y] ≥ dfn[x]
low[y]≥dfn[x] , x 必然是割点如果
x
x
x 是根节点, 如果只有一个子节点, 删去
x
x
x及与
x
x
x 相关联的边后, 图还是连通的, 不满足割点定义, 所以如果
x
x
x 是根节点, 还需要
x
x
x 有两个子节点
为了求出"点双连通分量", 需要在 t a r j a n tarjan tarjan 算法的过程中维护一个栈, 并按照如下方法维护栈中的元素:
- 当一个节点第一次访问时,把该节点入栈当割点判定法则中的条件
l
o
w
[
y
]
≥
d
f
n
[
x
]
low[y] ≥ dfn[x]
low[y]≥dfn[x] 成立时, 无论
x
x
x 是否为根, 都要:
(1):从栈顶不断弹出节点, 直至节点 y y y 被弹出
(2): 刚才弹出的所有节点与节点 x x x 一起构成一个 v − D C C v-DCC v−DCC(点双连通分量);
模板:
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp; // 分配时间戳
stk[++ tt] = u; //入栈
if(u == root && h[u] != -1)
{
dcc_cnt ++;
dcc[dcc_cnt].push_back(u);
return;
}
int cnt = 0; //记录节点u下, 子树的数量
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
if(low[y] >= dfn[x])
{
cnt ++;
if(u != root || cnt > 1) cut[u] = true; //如果是子树大于1, 或者是根节点,那么这个点就是割点
dcc_cnt ++;
int y;
do
{
y = stk[tt --];
dcc[dcc_cnt].push_back(y);
}while(y != j); //到j就退出了, 此时u还未被弹出
//u作为割点既可以和这个组成v-dcc也可以和另一个组成v-dcc
dcc[dcc_cnt].push_back(u);
}
else low[u] = min(low[u], dfn[j]);
}
}
}
边的双连通分量
要求边的双连通分量首先需要找到 桥,
x
x
x 与
y
y
y 之间是桥
⟺
iff
⟺
l
o
w
[
y
]
>
d
f
n
[
x
]
low[y] > dfn[x]
low[y]>dfn[x]
你会发现这和割点判断的很相似, 我们不妨来梳理一下
l
o
w
[
u
]
=
=
d
f
n
[
u
]
low[u] == dfn[u]
low[u]==dfn[u]
⟺
iff
⟺
u
u
u点是强连通分量的最高点
l
o
w
[
y
]
≥
d
f
n
[
x
]
low[y] ≥ dfn[x]
low[y]≥dfn[x]
⟺
iff
⟺
x
x
x是割点
l
o
w
[
y
]
>
d
f
n
[
x
]
low[y] > dfn[x]
low[y]>dfn[x]
⟺
iff
⟺
x
x
x 和
y
y
y 之间有桥
如何找到所有的边的双连通分量 ?
因为边的双连通分量是不包含桥的极大连通分量, 所以我们必须将所有的桥删掉
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++ timestamp; //分配时间戳
stk[++ tt] = u; //入栈
for(int i = h[u]; ~i; i = ne[i]) //遍历每条邻边
{
int j = e[i];
if(!dfn[j])
{
tarjan(j, i); //搜到底
low[u] = min(low[j], low[u]); //用j更新u
if(low[j] > dfn[u]) //判定为桥
is_bridge[i] = is_bridge[i ^ 1] = true;
}
//如果走到了j, 并且j不是由fa的反向边走过来的
else if(i != (fa ^ 1)) low[u] = min(low[u], dfn[j]);
}
if(dfn[u] == low[u]) //走到了该连通分量的最高点
{
int y;
++dcc_cnt;
do
{
y = stk[tt -- ]; //取出
id[y] = dcc_cnt; //分配编号
}while(y != u);
}
}
完结✿✿ヽ(°▽°)ノ✿! 给个赞吧!
