namori

ソースコード

from titan_pylib.graph.namori import Namori

view on github

展開済みコード

 1# from titan_pylib.graph.namori import Namori
 2class Namori:
 3
 4    def __init__(self, G: list[list[int]]):
 5        n = len(G)
 6        deg = [0] * n
 7        for v in range(n):
 8            for x in G[v]:
 9                deg[x] += 1
10        todo = [i for i, x in enumerate(deg) if x == 1]
11        cycle = set(range(n))
12        while todo:
13            v = todo.pop()
14            cycle.discard(v)
15            for x in G[v]:
16                deg[x] -= 1
17                if deg[x] == 1:
18                    todo.append(x)
19        tree = []
20        treeid = [-1] * n
21        now = 0
22        cycle_list = list(cycle)
23        for i in cycle_list:
24            tmp = []
25            todo = [i]
26            treeid[i] = now
27            while todo:
28                v = todo.pop()
29                tmp.append(v)
30                for x in G[v]:
31                    if treeid[x] != -1 or x in cycle:
32                        continue
33                    todo.append(x)
34                    treeid[x] = now
35            now += 1
36            tree.append(tmp)
37        # tree[i]:= cycle[i]を根とする木
38        # tree[i][0]は常に根
39        self.cycle = cycle_list
40        self.tree = tree
41        self.treeid = treeid
42
43    def same_tree(self, u: int, v: int) -> bool:
44        return self.treeid[u] == self.treeid[v]
45
46    def get_cycle(self):
47        return self.cycle
48
49    def get_tree(self):
50        return self.tree

仕様

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

Bases: object

get_cycle()[source]
get_tree()[source]
same_tree(u: int, v: int) → bool[source]