Source code for titan_pylib.graph.get_biconnected_components


[docs]
 1def get_biconnected_components(
 2    G: list[list[int]],
 3) -> tuple[list[list[int]], list[list[tuple[int, int]]]]:
 4    """``G`` を二重頂点連結分解します。
 5    :math:`O(n+m)` です。
 6
 7    Args:
 8      G (list[list[int]]): 隣接リストです。
 9
10    Returns:
11      tuple[list[list[int]], list[list[tuple[int, int]]]]: ``(頂点集合), (辺集合)`` のタプルです。
12    """
13    n = len(G)
14    order = [-1] * n
15    lowlink = [-1] * n
16    indx = [0] * n
17    cur_time = 0
18    stack = []
19    edge_ans = []
20    vertex_ans = []
21
22    def dfs(v: int, p: int = -1) -> None:
23        nonlocal cur_time
24        dfs_stack = [(v, -1)]
25        while dfs_stack:
26            v, p = dfs_stack.pop()
27            if v >= 0:
28                if indx[v] == len(G[v]):
29                    continue
30                if indx[v] == 0:
31                    order[v] = cur_time
32                    lowlink[v] = cur_time
33                    cur_time += 1
34                while indx[v] < len(G[v]):
35                    x = G[v][indx[v]]
36                    indx[v] += 1
37                    if x == p:
38                        continue
39                    if order[x] < order[v]:
40                        stack.append((min(v, x), max(v, x)))
41                    if order[x] == -1:
42                        if indx[v] != len(G[v]):
43                            dfs_stack.append((v, p))
44                        dfs_stack.append((~x, v))
45                        dfs_stack.append((x, v))
46                        break
47                    else:
48                        lowlink[v] = min(lowlink[v], order[x])
49            else:
50                x, v = ~v, p
51                lowlink[v] = min(lowlink[v], lowlink[x])
52                if lowlink[x] >= order[v]:
53                    min_vx, max_vx = min(x, v), max(x, v)
54                    this_edge_ans, this_vertex_ans = [], []
55                    while True:
56                        a, b = stack.pop()
57                        this_edge_ans.append((a, b))
58                        this_vertex_ans.append(a)
59                        this_vertex_ans.append(b)
60                        if min_vx == a and max_vx == b:
61                            break
62                    edge_ans.append(this_edge_ans)
63                    vertex_ans.append(list(set(this_vertex_ans)))
64
65    for root in range(n):
66        if order[root] == -1:
67            pre_len = len(vertex_ans)
68            dfs(root)
69            if len(vertex_ans) == pre_len:
70                vertex_ans.append([root])
71                edge_ans.append([])
72    return vertex_ans, edge_ans