Approach
Depth-first search
For ABC311 C — Find it!, 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
- 94 lines of Python from the credited upstream file abc311_c.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
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 3from typing import Any, List, Tuple4 5 678class CycleDetection:9 pending: int = -110 11 def __init__(self, vertex_count: int, graph: List[List[Tuple[int, int]]]) -> None:12 self.vertex_count: int = vertex_count13 self.graph: List[List[Tuple[int, int]]] = graph14 self.seen: List[bool] = [False] * self.vertex_count15 self.finished: List[bool] = [False] * self.vertex_count16 self.history: List[Any] = []17 18 def detect(self, is_prohibit_reverse: bool = True) -> List[Any]:19 pos = self.pending20 21 for vertex in range(self.vertex_count):22 if self.seen[vertex]:23 continue24 25 self.history.clear()26 pos = self._dfs(vertex, self.pending, is_prohibit_reverse)27 28 if pos != self.pending:29 return self._reconstruct(pos)30 31 return []32 33 def _reconstruct(self, pos: int) -> List[int]:34 cycle: List[Any] = []35 36 while self.history:37 cur = self.history.pop()38 cycle.append(cur)39 40 if cur == pos:41 break42 43 return cycle[::-1]44 45 def _dfs(self, cur: int, parent: int, is_prohibit_reverse: bool = True) -> int:46 self.seen[cur] = True47 self.history.append(parent)48 49 for to, id in self.graph[cur]:50 if is_prohibit_reverse and (to == parent):51 continue52 if self.finished[to]:53 continue54 55 56 if self.seen[to] and not self.finished[to]:57 self.history.append(cur)58 return to59 60 pos = self._dfs(to, cur, is_prohibit_reverse)61 62 if pos != self.pending:63 return pos64 65 self.finished[cur] = True66 self.history.pop()67 return self.pending68 69 70def main():71 import sys72 73 sys.setrecursionlimit(10**8)74 75 input = sys.stdin.readline76 77 n = int(input())78 a = list(map(int, input().split()))79 graph = [[] for _ in range(n)]80 81 for i, ai in enumerate(a):82 ai -= 183 graph[i].append((ai, i))84 85 cd = CycleDetection(vertex_count=n, graph=graph)86 results = cd.detect(is_prohibit_reverse=False)87 88 print(len(results))89 print(*map(lambda x: x + 1, results))90 91 92if __name__ == "__main__":93 main()94