Source code for titan_pylib.graph.functional_graph


[docs]
 1class FunctionalGraph:
 2
 3    def __init__(self, A: list[int]) -> None:
 4        # i -> A[i]
 5        n = len(A)
 6        G = [[] for _ in range(n)]
 7        revG = [[] for _ in range(n)]
 8        for i, p in enumerate(A):
 9            G[i].append(p)
10            revG[p].append(i)
11
12        dataG = [[] for _ in range(n)]
13        data_cycle = []
14        cycle_ids = [-1] * n
15        cycle_id_now = 0
16
17        def calc(v: int):
18            nonlocal cycle_id_now
19            # vを持つ連結成分に対して処理する
20            todo = [v]
21            seen[v] = True
22            cycle = []
23            while todo:
24                v = todo.pop()
25                cycle.append(v)
26                for x in G[v]:
27                    if seen[x]:
28                        cycle.append(x)
29                        break
30                    seen[x] = True
31                    todo.append(x)
32            goal = cycle.pop()
33            for i in range(len(cycle)):
34                if cycle[i] == goal:
35                    cycle = cycle[i:]
36                    break
37            data_cycle.append(cycle)
38            for c in cycle:
39                seen_cycle[c] = True
40                cycle_ids[c] = cycle_id_now
41            for root in cycle:
42                todo = [root]
43                while todo:
44                    v = todo.pop()
45                    seen[v] = True
46                    cycle_ids[v] = cycle_id_now
47                    for x in revG[v]:
48                        if seen_cycle[x]:
49                            continue
50                        todo.append(x)
51                        dataG[v].append(x)
52                        dataG[x].append(v)
53            cycle_id_now += 1
54
55        seen_cycle = [False] * n
56        seen = [False] * n
57        for i in range(n):
58            if seen[i]:
59                continue
60            calc(i)
61        # vが属する連結成分に含まれるサイクルが、data_cycleの何番目か
62        # ex: https://atcoder.jp/contests/abc357/submissions/59220690
63        self.cycle_ids = cycle_ids
64        self.data_cycle = data_cycle
65        self.dataG = dataG