Source code for titan_pylib.graph.dfs_tree

 1from titan_pylib.others.antirec import antirec
 2
 3

[docs]
 4class DFSTree:
 5
 6    def __init__(self, G: list[list[int]]) -> None:
 7        self.n = len(G)
 8        self.G = G
 9        self.order = [-1] * self.n
10        self.low = [self.n] * self.n
11        self.par = [-1] * self.n
12        self.dfs_forest = [[] for _ in range(self.n)]
13        self._calc_lowlink()
14
15    def _calc_lowlink(self) -> None:
16        t = 0
17        order, low, par, dfs_forest = self.order, self.low, self.par, self.dfs_forest
18        G = self.G
19
20        @antirec
21        def dfs(v: int, p: int = -1):
22            nonlocal t
23            par[v] = p
24            order[v] = t
25            low[v] = t
26            t += 1
27            seen_p = False
28            for x in G[v]:
29                if x == p and not seen_p:
30                    seen_p = True
31                    continue
32                if order[x] == -1:
33                    dfs_forest[v].append(x)
34                    dfs_forest[x].append(v)
35                    yield dfs(x, v)
36                    low[v] = min(low[v], low[x])
37                else:
38                    low[v] = min(low[v], order[x])
39            yield
40
41        for v in range(self.n):
42            if order[v] == -1:
43                dfs(v)
44

[docs]
45    def get_bridge(self) -> list[tuple[int, int]]:
46        order, low, par, dfs_forest = self.order, self.low, self.par, self.dfs_forest
47        bridge = []
48        for v in range(self.n):
49            if par[v] != -1:
50                continue
51            todo = [v]
52            while todo:
53                v = todo.pop()
54                for x in dfs_forest[v]:
55                    if x == par[v]:
56                        continue
57                    if order[v] < low[x]:
58                        bridge.append((min(v, x), max(v, x)))
59                    todo.append(x)
60        return bridge

61

[docs]
62    def get_two_edge_connected_components(self):
63        """二辺連結成分分解"""
64        order, low, par, dfs_forest = self.order, self.low, self.par, self.dfs_forest
65        ids = [-1] * self.n
66        E = []
67        idx = 0
68        for v in range(self.n):
69            if par[v] != -1:
70                continue
71            ids[v] = idx
72            todo = [v]
73            while todo:
74                v = todo.pop()
75                for x in dfs_forest[v]:
76                    if x == par[v]:
77                        continue
78                    if order[v] < low[x]:
79                        idx += 1
80                        ids[x] = idx
81                        E.append((ids[v], idx))
82                    else:
83                        ids[x] = ids[v]
84                    todo.append(x)
85            idx += 1
86        gropus = [[] for _ in range(idx)]
87        F = [[] for _ in range(idx)]
88        for v in range(self.n):
89            gropus[ids[v]].append(v)
90        for u, v in E:
91            F[u].append(v)
92            F[v].append(u)
93        return ids, gropus, F