Source code for titan_pylib.graph.get_articulation_points

 1from types import GeneratorType
 2
 3"""Return articulation points. / O(|V|+|E|)"""
 4
 5
 6# https://algo-logic.info/articulation-points/

[docs]
 7def get_articulation_points(G: list[list[int]]) -> list[int]:
 8    n = len(G)
 9    order = [-1] * n
10    res: list[int] = []
11    cnt = 0
12
13    def antirec(func):
14        # 再帰用デコレータ
15        # yieldにするのを忘れないこと
16        # 参考: https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py
17        stack = []
18
19        def wrappedfunc(*args, **kwargs):
20            if stack:
21                return func(*args, **kwargs)
22            to = func(*args, **kwargs)
23            while True:
24                if isinstance(to, GeneratorType):
25                    stack.append(to)
26                    to = next(to)
27                else:
28                    stack.pop()
29                    if not stack:
30                        break
31                    to = stack[-1].send(to)
32            return to
33
34        return wrappedfunc
35
36    @antirec
37    def dfs(v: int, p: int) -> int:
38        nonlocal cnt
39        r_min = order[v] = cnt
40        fcnt = 0
41        p_art = 0
42        cnt += 1
43        for w in G[v]:
44            if w == p:
45                continue
46            if order[w] == -1:
47                ret = yield dfs(w, v)
48                p_art |= order[v] <= ret
49                r_min = min(r_min, ret)
50                fcnt += 1
51            else:
52                r_min = min(r_min, order[w])
53        p_art |= r_min == order[v] and len(G[v]) > 1
54        if (p == -1 and fcnt > 1) or (p != -1 and p_art):
55            res.append(v)
56        yield r_min
57
58    if G:
59        dfs(0, -1)
60    return res