Source code for titan_pylib.graph.get_bridge

 1from titan_pylib.others.antirec import antirec
 2
 3

[docs]
 4def get_bridge(G: list[list[int]]) -> tuple[list[int], list[tuple[int, int]]]:
 5    # ref: https://algo-logic.info/bridge-lowlink/
 6
 7    n = len(G)
 8    bridges = []
 9    articulation_points = []
10    order = [-1] * n
11    lowlink = [0] * n
12    cur_time = 0
13
14    @antirec
15    def dfs(v: int, p: int = -1):
16        nonlocal cur_time
17        order[v] = cur_time
18        lowlink[v] = cur_time
19        cur_time += 1
20        cnt = 0
21        flag = False
22        for x in G[v]:
23            if x == p:
24                continue
25            if order[x] == -1:
26                cnt += 1
27                yield dfs(x, v)
28                if p != -1 and order[v] <= lowlink[x]:
29                    flag = True
30                lowlink[v] = min(lowlink[v], lowlink[x])
31                if lowlink[x] > order[v]:
32                    bridges.append((x, v))
33            else:
34                lowlink[v] = min(lowlink[v], order[x])
35        if p == -1 and cnt >= 2:
36            flag = True
37        if flag:
38            articulation_points.append(v)
39        yield
40
41    for v in range(n):
42        if order[v] == -1:
43            dfs(v)
44    return articulation_points, bridges