get_bridge

ソースコード

from titan_pylib.graph.get_bridge import get_bridge

view on github

展開済みコード

  1# from titan_pylib.graph.get_bridge import get_bridge
  2# from titan_pylib.others.antirec import antirec
  3from types import GeneratorType
  4
  5# ref: https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py
  6# ref: https://twitter.com/onakasuita_py/status/1731535542305907041
  7
  8
  9def antirec(func):
 10    stack = []
 11
 12    def wrappedfunc(*args, **kwargs):
 13        if stack:
 14            return func(*args, **kwargs)
 15        to = func(*args, **kwargs)
 16        while True:
 17            if isinstance(to, GeneratorType):
 18                stack.append(to)
 19                to = next(to)
 20            else:
 21                stack.pop()
 22                if not stack:
 23                    break
 24                to = stack[-1].send(to)
 25        return to
 26
 27    return wrappedfunc
 28
 29
 30def antirec_cache(func):
 31    stack = []
 32    memo = {}
 33    args_list = []
 34
 35    def wrappedfunc(*args):
 36        args_list.append(args)
 37        if stack:
 38            return func(*args)
 39        to = func(*args)
 40        while True:
 41            if args_list[-1] in memo:
 42                res = memo[args_list.pop()]
 43                if not stack:
 44                    return res
 45                to = stack[-1].send(res)
 46                continue
 47            if isinstance(to, GeneratorType):
 48                stack.append(to)
 49                to = next(to)
 50            else:
 51                memo[args_list.pop()] = to
 52                stack.pop()
 53                if not stack:
 54                    break
 55                to = stack[-1].send(to)
 56        return to
 57
 58    return wrappedfunc
 59
 60
 61def get_bridge(G: list[list[int]]) -> tuple[list[int], list[tuple[int, int]]]:
 62    # ref: https://algo-logic.info/bridge-lowlink/
 63
 64    n = len(G)
 65    bridges = []
 66    articulation_points = []
 67    order = [-1] * n
 68    lowlink = [0] * n
 69    cur_time = 0
 70
 71    @antirec
 72    def dfs(v: int, p: int = -1):
 73        nonlocal cur_time
 74        order[v] = cur_time
 75        lowlink[v] = cur_time
 76        cur_time += 1
 77        cnt = 0
 78        flag = False
 79        for x in G[v]:
 80            if x == p:
 81                continue
 82            if order[x] == -1:
 83                cnt += 1
 84                yield dfs(x, v)
 85                if p != -1 and order[v] <= lowlink[x]:
 86                    flag = True
 87                lowlink[v] = min(lowlink[v], lowlink[x])
 88                if lowlink[x] > order[v]:
 89                    bridges.append((x, v))
 90            else:
 91                lowlink[v] = min(lowlink[v], order[x])
 92        if p == -1 and cnt >= 2:
 93            flag = True
 94        if flag:
 95            articulation_points.append(v)
 96        yield
 97
 98    for v in range(n):
 99        if order[v] == -1:
100            dfs(v)
101    return articulation_points, bridges

仕様

get_bridge(G: list[list[int]]) → tuple[list[int], list[tuple[int, int]]][source]