Source code for titan_pylib.graph.namori


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

[docs]
42    def same_tree(self, u: int, v: int) -> bool:
43        return self.treeid[u] == self.treeid[v]

44

[docs]
45    def get_cycle(self):
46        return self.cycle

47

[docs]
48    def get_tree(self):
49        return self.tree