Approach
Depth-first search
For ABC357 E — Reachability in Functional Graph, 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
- 164 lines of Python from the credited upstream file abc357_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 3import sys4import typing5 6 789class SCCGraph:10 def __init__(self, n: int = 0) -> None:11 self._internal = _SCCGraph(n)12 13 def add_edge(self, from_vertex: int, to_vertex: int) -> None:14 n = self._internal.num_vertices()15 16 assert 0 <= from_vertex < n17 assert 0 <= to_vertex < n18 19 self._internal.add_edge(from_vertex, to_vertex)20 21 def scc(self) -> typing.List[typing.List[int]]:22 return self._internal.scc()23 24 25class CSR:26 def __init__(self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:27 self.start = [0] * (n + 1)28 self.elist = [0] * len(edges)29 30 for e in edges:31 self.start[e[0] + 1] += 132 33 for i in range(1, n + 1):34 self.start[i] += self.start[i - 1]35 36 counter = self.start.copy()37 38 for e in edges:39 self.elist[counter[e[0]]] = e[1]40 counter[e[0]] += 141 42 43class _SCCGraph:44 """45 Reference:46 R. Tarjan,47 Depth-First Search and Linear Graph Algorithms48 """49 50 def __init__(self, n: int) -> None:51 self._n = n52 self._edges: typing.List[typing.Tuple[int, int]] = []53 54 def num_vertices(self) -> int:55 return self._n56 57 def add_edge(self, from_vertex: int, to_vertex: int) -> None:58 self._edges.append((from_vertex, to_vertex))59 60 def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:61 g = CSR(self._n, self._edges)62 now_ord = 063 group_num = 064 visited = []65 low = [0] * self._n66 order = [-1] * self._n67 ids = [0] * self._n68 69 sys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit()))70 71 def dfs(v: int) -> None:72 nonlocal now_ord73 nonlocal group_num74 nonlocal visited75 nonlocal low76 nonlocal order77 nonlocal ids78 79 low[v] = now_ord80 order[v] = now_ord81 now_ord += 182 visited.append(v)83 84 for i in range(g.start[v], g.start[v + 1]):85 to = g.elist[i]86 87 if order[to] == -1:88 dfs(to)89 low[v] = min(low[v], low[to])90 else:91 low[v] = min(low[v], order[to])92 93 if low[v] == order[v]:94 while True:95 u = visited[-1]96 visited.pop()97 order[u] = self._n98 ids[u] = group_num99 100 if u == v:101 break102 103 group_num += 1104 105 for i in range(self._n):106 if order[i] == -1:107 dfs(i)108 109 for i in range(self._n):110 ids[i] = group_num - 1 - ids[i]111 112 return group_num, ids113 114 def scc(self) -> typing.List[typing.List[int]]:115 ids = self.scc_ids()116 group_num = ids[0]117 counts = [0] * group_num118 119 for x in ids[1]:120 counts[x] += 1121 122 groups: typing.List[typing.List[int]] = [[] for _ in range(group_num)]123 124 for i in range(self._n):125 groups[ids[1][i]].append(i)126 127 return groups128 129 130def main():131 import sys132 133 input = sys.stdin.readline134 135 n = int(input())136 a = list(map(lambda x: int(x) - 1, input().split()))137 g = SCCGraph(n)138 139 140 141 for i, ai in enumerate(a):142 g.add_edge(i, ai)143 144 counts = [0] * n145 146 147 for group in g.scc()[::-1]:148 size = len(group)149 g0 = group[0]150 151 152 if size >= 2 or g0 == a[g0]:153 for g in group:154 counts[g] = size155 else:156 157 counts[g0] = counts[a[g0]] + 1158 159 print(sum(counts))160 161 162if __name__ == "__main__":163 main()164