Approach
Depth-first search
For ABC245 F — Endless Walk, 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
- 171 lines of Python from the credited upstream file abc245_f.py.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup, cached states.
- 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 groups 130 131 132def main():133 import sys134 135 input = sys.stdin.readline136 137 n, m = map(int, input().split())138 to = [[] for _ in range(n)]139 scc = SCCGraph(n)140 141 for _ in range(m):142 ai, bi = map(int, input().split())143 ai -= 1144 bi -= 1145 146 scc.add_edge(ai, bi)147 to[bi].append(ai)148 149 groups = scc.scc()150 dp = [0] * (n + 1)151 152 153 for group in groups:154 if len(group) <= 1:155 continue156 157 for v in group:158 dp[v] = 1159 160 161 for group in groups[::-1]:162 for x in group:163 for y in to[x]:164 dp[y] |= dp[x]165 166 print(sum(dp))167 168 169if __name__ == "__main__":170 main()171