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