图的联通性python代码模板

Chuanhua Yu 发布于

最后更新于

图的联通性代码模板

[TOC]

  • 关于 和 缩点的应用可能结合倍增 算法，多次回答无向图上两点之间的必经边、必经点的询问。

算法与无向图连通性

时间戳

在图的深度优先遍历中，按照每个结点第一次被访问的顺序，依次给予 个结点 ~ 的整数标记，该标记就被称为“时间戳”，记为 。

搜索树

在无向连通图中任选一个结点进行 ，每个结点只访问一次。所有发生递归的边 构成一棵树，我们把它称为“无向连通图的搜索树”。一般的无向连通图的各个连通块的搜索树构成无向图的搜索森林。

追溯值

返祖边：搜索树上的一个点连向其祖先结点的边

横插边：搜索树上一个点连向它另一条支链上的点的边（只存在于有向图）

定义为当前点及其子树的仅通过一条返祖边能连到 值最小的点

是树边:

是返祖边:

什么样的点是割点？

  1. 有多个儿子的根结点。
  2. 子树中不存在跨越自己连向上方的返祖边

什么样的边是桥(割边)？

  • 是树边，且下侧的点及其子树中不存在连向上侧的返祖边，即搜索树上一结点 及其子结点 满足： 。

求割点代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def tarjan(x):
    global cnt # 当前时间戳
    cnt += 1
    dfn[x] = low[x] = cnt
    flag = 0  # 子树中不满足条件的点的数量
    for y,w in g[x]:
        if not dfn[y]:
            tarjan(y)
            low[x] = min(low[x], low[y]) # 树边更新low值
            if low[y] >= dfn[x]: # 返祖边在x下侧，只要有x就是割点
                flag += 1
                if (x != root or flag > 1): boo[x] = 1 # 如果是root，还要保证儿子数大于1
        else: low[x] = min(low[x], dfn[y]) # 非树边更新 low值

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int, input().split())
    if x == y: continue
    g[x].append(y)
    g[y].append(x)

cnt = 0  # 用于记录当前时间戳
dfn, boo = [0]*(n+1), [0]*(n+1) # dfn:时间戳, boo:是否为割点
low = [i for i in range(n+1)]
for i in range(1,n+1):
    if not dfn[i]: 
        root = i
    	tarjan(i)

求桥(割边)代码

这是一个求无向图桥的代码，因为是无向图所以从每个点 出发都能到其父亲结点 。根据 的计算方法， 是树上的边，且 不是 的子结点，故不能用 来更新，但是如果只记录每个结点的父亲结点，则不能处理重边的情况，有重边时，重边也属于 的返祖边，故可以用 来更新 。一个比较好的处理方法是利用“成对变换”的技巧，当沿着编号为 的边递归进入了结点 则忽略从 出发编号为 ^ 边，通过其他边计算 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def add(x,y,z):
    global tot
    tot += 1
    ver[tot],edge[tot] = y,z
    nxt[tot],head[x] = head[x],tot
    
def tarjan(x, in_edge):
    global cnt  # 在solve里面用 nonlocal cnt
    cnt += 1
    dfn[x] = low[x] = cnt
    i = head[x]
    while i:
        y = ver[i]
        if not dfn[y]:
            tarjan(y,i)
            low[x] = min(low[x], low[y])
            if low[y] > dfn[x]: # (x,y) 为桥
                bridge[i] = bridge[i^1] = 1
        elif i != (in_edge^1): # 忽略反向边
            low[x] = min(low[x],dfn[y])
        i = nxt[i]
    
n,m = map(int, input().split())
head = [0]*(n+1)
ver,edge,nxt = [0]*(2*m+1),[0]*(2*m+1),[0]*(2*m+1)
tot = 0

for i in range(m):
    x,y,z = map(int, input().split())
    add(x,y,z)
    add(y,x,z)

bridge = [0]*(2*m+1)
dfn,low = [0]*(n+1), [i for i in range(n+1)]
cnt = 0
for i in range(1,n+1):
    if not dfn[i]:tarjan(i,0)
for i in range(2,tot+1,2):
    if bridge[i]: print(ver[i^1],ver[i])

边双连通分量()

​ 把割边删了之后，每一个连通块都是一个边双连通分量，可以用 数组记录结点属于的便双连通分量的编号。

缩点

​ 把每个 看成一个结点，把桥 看成连接 和 的无向边，会产生一棵树(若原来的无向图不连通，则产生森林)，python代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import sys
input = sys.stdin.readline

def add(x,y,z):
    global tot
    tot += 1
    ver[tot],edge[tot] = y,z
    nxt[tot],head[x] = head[x], tot

def tarjan(x, in_edge):
    global cnt  # 在solve里面用 nonlocal cnt
    cnt += 1
    dfn[x] = low[x] = cnt
    i = head[x]
    while i:
        y = ver[i]
        if not dfn[y]: # 是树边
            tarjan(y,i)
            low[x] = min(low[x], low[y])
            if low[y] > dfn[x]: # (x,y) 为桥
                bridge[i] = bridge[i^1] = 1
        elif i != (in_edge^1): # 忽略反向边
            low[x] = min(low[x], dfn[y])
        i = nxt[i]

def dfs(x):  
    """类似找连通块的方法对 e-DCC 染色"""
    c[x] = dcc
    i = head[x]
    while i:
        y = ver[i]
        if c[y] or bridge[i]: continue
        dfs(y)
        i = nxt[i]

n,m = map(int, input().split())
head = [0]*(n+1)
ver,nxt,edge = [0]*(2*m+1),[0]*(2*m+1),[0]*(2*m+1)
tot = 0
for i in range(m):
    x,y,z = map(int, input().split())
    add(x,y,z)
    add(y,x,z)

bridge = [0]*(m*2+1)
dfn,low = [0]*(n+1),[i for i in range(n+1)]
cnt = 0
for i in range(1,n+1):
    if not dfn[i]: tarjan(i, 0)

c,dcc = [0]*(n+1), 0
for i in range(1,n+1):
    if not c[i]:
        dcc += 1
        dfs(i)

点双连通分量()

求

​ 这里需要注意的是割点可能属于多个点双连通分量，为了求出点双连通分量，需要在 算法的过程中维护一个栈，并按照如下方法维护栈中元素。

  1. 当一个结点第一次被访问时，把该结点入栈。
  2. 当割点判定法则中的条件 成立时，无论 是否为根，都要：
    • 1）从栈顶不断弹出结点，直至结点 被弹出。
    • 2）刚才弹出的所有结点与结点 共同构成一个 。

缩点

的缩点比 的缩点复杂——因为一个割点可能属于多个 。设图有 个割点和 个 。我们建立一张包含 个结点的新图，把每个 和每个割点都作为新图中的结点，并在每个割点和包含它的所有 之间连边。这张新图其实是一张树或森林。

python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import sys

def tarjan(x):
    global cnt,tot # 当前时间戳
    cnt += 1
    dfn[x] = low[x] = cnt
    st.append(x)
    if x == root and len(g[x]) == 0:
        tot += 1
        dcc[tot].append(x)
        return
    flag = 0  # 子树中不满足条件的点的数量
    for y in g[x]:
        if not dfn[y]:
            tarjan(y)
            low[x] = min(low[x], low[y]) # 树边更新low值
            if low[y] >= dfn[x]: # 返祖边在x下侧，只要有x就是割点
                flag,tot= flag + 1, tot + 1
                if (x != root or flag > 1): boo[x] = 1 # 如果是root，还要保证儿子数大于1
                while st[-1] != x:
                    dcc[tot].append(st.pop())
                dcc[tot].append(x)
        else: low[x] = min(low[x], dfn[y]) # 非树边更新 low值

n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int, input().split())
    if x == y: continue
    g[x].append(y)
    g[y].append(x)

"""求v-DCC"""
cnt,tot = 0,0  # 用于记录当前时间戳, dcc编号
dfn, boo = [0]*(n+1), [0]*(n+1) # dfn:时间戳, boo:是否为割点
low = [i for i in range(n+1)]
st,dcc = [],[[] for i in range(n+1)]  # stack, v-DCC
for i in range(1,n+1):
    if not dfn[i]:
        root = i
        tarjan(i)

"""v-DCC 缩点"""
cnt = tot
new_id = [0]*(n+1)
for i in range(1,n+1):
    if boo[i]:  # 给每个割点一个新的编号(从 cnt+1 开始)
        cnt += 1
        new_id[i] = cnt
gg = [[] for _ in range(cnt + 1)]
c = [0]*(n+1) # v-DCC 染色
for i in range(1,tot+1):
    for j in range(len(dcc[i])):
        x = dcc[i][j]
        if boo[x]:
            gg[i].append(new_id[x])
            gg[new_id[x]].append(i)
        else: c[x] = i  # 除割点外，其他点仅属于1个 v-DCC

有向图的连通性

一些概念

​ 给定有向图，若存在 ，满足从 出发能够到达 中所有的点则称 是一个“流图”，记为 ，其中 为流图的源点。流图中每条有向边 必然是以下四种之一：1、树边 2、前向边 3、返祖边(后向边) 4、横插边。

​ 有向图的极大强连通子图称为“强连通分量”。

1、 算法

​ 对原图进行一次 ，分成若干棵树，再以第一次搜索的出栈顺序对原图的返图进行 ，和 能到的是在同一个连通分量中。

2、 算法与有向图的强连通分量

强连通分量 以及 缩点

​ 在这里 算法的的基本思路是对于每一个点，尽量找到能与他构成环的所有结点。为了找到通过“后向边”和“横插边”构成的环， 算法在 的同时维护一个栈，当访问到结点 时，栈中需要保存以下两类结点：

  1. 搜索树上 的祖先结点，记为集合 。设 。若存在后向边 ，则 与 到 的路径一定形成环。
  2. 已经访问过并且存在一条路径到达 的结点。设 是这样一个点，从 出发存在一条路径到达 。若存在横插边 ，则 、到的路径、到的路径 形成一个环。

综上所述，栈中结点就是能与从 出发的“后向边”和“横插边”形成环的结点。

​ 设 表示流图的搜索树中以 为根的子树。 定义为从 出发的有向边能连接到的还在栈中 值最小的点。根据定义， 算法计算“追溯值” 的步骤如下：

  1. 当结点 第一次被访问时，把 入栈，初始化 。
  2. 扫描 的每条出边 :
    • 若 没被访问过，则说明 是树边，递归访问 ，从 回溯后，令 。
    • 若 被访问过，并且 在栈中，则令 。
  3. 从 回溯之前，判断是否有 。若成立，则不断从栈中弹出结点，直至 出栈。意味着就是这个强连通分量中在搜索树上最高的点

python code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import sys
input = sys.stdin.readline

def tarjan(x):
    global cnt,tot # 当前时间戳
    cnt += 1
    dfn[x] = low[x] = cnt
    st.append(x)
    ins[x] = 1
    for y in g[x]:
        if not dfn[y]:
            tarjan(y)
            low[x] = min(low[x], low[y])
        elif ins[y]:
            low[x] = min(low[x],dfn[y])
    if dfn[x] == low[x]:
        tot += 1
        while st[-1] != x:
            y = st.pop()
            ins[y] = 0
            c[y] = tot, scc[tot].append(y)
        y = st.pop()
        ins[y] = 0
        c[y] = tot, scc[tot].append(y)
        
cnt,tot = 0,0  # 用于记录当前时间戳, scc编号
n,m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int, input().split())
    if x == y: continue
    g[x].append(y)
    g[y].append(x)

"""求SCC"""
dfn,c = [0]*(n+1),[0]*(n+1) # dfn:时间戳, c:SCC编号
low = [i for i in range(n+1)]
scc = [[] for _ in range(n+1)]
st,ins = [],[0]*(n+1) # stack, if in stack or not
for i in range(1,n+1):
    if not dfn[i]: tarjan(i)

"""SCC缩点"""
gc = [[] for _ in range(tot+1)]
for x in range(1,n+1):
    for y in g[x]:
        if c[x] == c[y]: continue
        g[c[x]].append(c[y])
smile是对你的礼貌

smile是对你的礼貌

在思维的迷宫里，有的人凭天生的灵感直奔终点； 有的人以持久的勤勉，铸造出适合自己的罗盘！

33
2
13
NOTICE

这是我的个人博客，主要发布一些算法竞赛相关题解和人工智能相关的技术与知识，页面最下面可以访问我的Github和知乎，可以通过下面链接访问我的CSDN https://blog.csdn.net/smile__everydays?spm=1000.2115.3001.5343

CATEGORYS
TAGS
DP Machine Learning XCPC div2 python模板 介绍 图匹配 图论 技术部寒假算法培训 最小生成树 牛客竞赛 蓝书 题目汇总