Approach
Depth-first search
For ABC296 E — Transition Game, the implementation follows one branch at a time, making it suitable for components, trees, backtracking, or dependency exploration.
- Define the state carried into one recursive or stack frame.
- Mark or choose the current state before exploring children.
- Combine child results or undo the choice when the branch finishes.
Code notes
- 166 lines of Python from the credited upstream file abc296_e.py.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup.
- No explicit loop blocks detected, together with recursive traversal.
Complexity
Count unique states for graph traversal; for backtracking, count the branching factor and maximum depth.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4import sys5import typing6 7 8910class SCCGraph:11 def __init__(self, n: int = 0) -> None:12 self._internal = _SCCGraph(n)13 14 def add_edge(self, from_vertex: int, to_vertex: int) -> None:15 n = self._internal.num_vertices()16 17 assert 0 <= from_vertex < n18 assert 0 <= to_vertex < n19 20 self._internal.add_edge(from_vertex, to_vertex)21 22 def scc(self) -> typing.List[typing.List[int]]:23 return self._internal.scc()24 25 26class CSR:27 def __init__(28 self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:29 self.start = [0] * (n + 1)30 self.elist = [0] * len(edges)31 32 for e in edges:33 self.start[e[0] + 1] += 134 35 for i in range(1, n + 1):36 self.start[i] += self.start[i - 1]37 38 counter = self.start.copy()39 40 for e in edges:41 self.elist[counter[e[0]]] = e[1]42 counter[e[0]] += 143 44 45class _SCCGraph:46 '''47 Reference:48 R. Tarjan,49 Depth-First Search and Linear Graph Algorithms50 '''51 52 def __init__(self, n: int) -> None:53 self._n = n54 self._edges: typing.List[typing.Tuple[int, int]] = []55 56 def num_vertices(self) -> int:57 return self._n58 59 def add_edge(self, from_vertex: int, to_vertex: int) -> None:60 self._edges.append((from_vertex, to_vertex))61 62 def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:63 g = CSR(self._n, self._edges)64 now_ord = 065 group_num = 066 visited = []67 low = [0] * self._n68 order = [-1] * self._n69 ids = [0] * self._n70 71 sys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit()))72 73 def dfs(v: int) -> None:74 nonlocal now_ord75 nonlocal group_num76 nonlocal visited77 nonlocal low78 nonlocal order79 nonlocal ids80 81 low[v] = now_ord82 order[v] = now_ord83 now_ord += 184 visited.append(v)85 86 for i in range(g.start[v], g.start[v + 1]):87 to = g.elist[i]88 89 if order[to] == -1:90 dfs(to)91 low[v] = min(low[v], low[to])92 else:93 low[v] = min(low[v], order[to])94 95 if low[v] == order[v]:96 while True:97 u = visited[-1]98 visited.pop()99 order[u] = self._n100 ids[u] = group_num101 102 if u == v:103 break104 105 group_num += 1106 107 for i in range(self._n):108 if order[i] == -1:109 dfs(i)110 111 for i in range(self._n):112 ids[i] = group_num - 1 - ids[i]113 114 return group_num, ids115 116 def scc(self) -> typing.List[typing.List[int]]:117 ids = self.scc_ids()118 group_num = ids[0]119 counts = [0] * group_num120 121 for x in ids[1]:122 counts[x] += 1123 124 groups: typing.List[typing.List[int]] = [[] for _ in range(group_num)]125 126 for i in range(self._n):127 groups[ids[1][i]].append(i)128 129 return groups130 131 132def main():133 import sys134 135 input = sys.stdin.readline136 137 n = int(input())138 a = list(map(int, input().split()))139 scc = SCCGraph(n)140 ans = 0141 142 143 144 145 146 147 148 for i, ai in enumerate(a):149 ai -= 1150 scc.add_edge(i, ai)151 152 if i == ai:153 ans += 1154 155 for vertex in scc.scc():156 size = len(vertex)157 158 if size >= 2:159 ans += size160 161 print(ans)162 163 164if __name__ == "__main__":165 main()166