get_articulation_points

ソースコード

from titan_pylib.graph.get_articulation_points import get_articulation_points

view on github

展開済みコード

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

仕様

get_articulation_points(G: list[list[int]]) → list[int][source]