dfs_tree

ソースコード

from titan_pylib.graph.dfs_tree import DFSTree

view on github

展開済みコード

 1# 展開に失敗しました
 2from titan_pylib.others.antirec import antirec
 3
 4
 5class DFSTree:
 6
 7    def __init__(self, G: list[list[int]]) -> None:
 8        self.n = len(G)
 9        self.G = G
10        self.order = [-1] * self.n
11        self.low = [self.n] * self.n
12        self.par = [-1] * self.n
13        self.dfs_forest = [[] for _ in range(self.n)]
14        self._calc_lowlink()
15
16    def _calc_lowlink(self) -> None:
17        t = 0
18        order, low, par, dfs_forest = self.order, self.low, self.par, self.dfs_forest
19        G = self.G
20
21        @antirec
22        def dfs(v: int, p: int = -1):
23            nonlocal t
24            par[v] = p
25            order[v] = t
26            low[v] = t
27            t += 1
28            seen_p = False
29            for x in G[v]:
30                if x == p and not seen_p:
31                    seen_p = True
32                    continue
33                if order[x] == -1:
34                    dfs_forest[v].append(x)
35                    dfs_forest[x].append(v)
36                    yield dfs(x, v)
37                    low[v] = min(low[v], low[x])
38                else:
39                    low[v] = min(low[v], order[x])
40            yield
41
42        for v in range(self.n):
43            if order[v] == -1:
44                dfs(v)
45
46    def get_bridge(self) -> list[tuple[int, int]]:
47        order, low, par, dfs_forest = self.order, self.low, self.par, self.dfs_forest
48        bridge = []
49        for v in range(self.n):
50            if par[v] != -1:
51                continue
52            todo = [v]
53            while todo:
54                v = todo.pop()
55                for x in dfs_forest[v]:
56                    if x == par[v]:
57                        continue
58                    if order[v] < low[x]:
59                        bridge.append((min(v, x), max(v, x)))
60                    todo.append(x)
61        return bridge
62
63    def get_two_edge_connected_components(self):
64        """二辺連結成分分解"""
65        order, low, par, dfs_forest = self.order, self.low, self.par, self.dfs_forest
66        ids = [-1] * self.n
67        E = []
68        idx = 0
69        for v in range(self.n):
70            if par[v] != -1:
71                continue
72            ids[v] = idx
73            todo = [v]
74            while todo:
75                v = todo.pop()
76                for x in dfs_forest[v]:
77                    if x == par[v]:
78                        continue
79                    if order[v] < low[x]:
80                        idx += 1
81                        ids[x] = idx
82                        E.append((ids[v], idx))
83                    else:
84                        ids[x] = ids[v]
85                    todo.append(x)
86            idx += 1
87        gropus = [[] for _ in range(idx)]
88        F = [[] for _ in range(idx)]
89        for v in range(self.n):
90            gropus[ids[v]].append(v)
91        for u, v in E:
92            F[u].append(v)
93            F[v].append(u)
94        return ids, gropus, F

仕様

class DFSTree(G: list[list[int]])[source]

Bases: object

get_bridge() → list[tuple[int, int]][source]
get_two_edge_connected_components()[source]

二辺連結成分分解