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