Approach
Breadth-first search
For ABC313 B — Who is Saikyo?, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 65 lines of Python from the credited upstream file abc313_b.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected, together with recursive traversal.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def main():5 import sys6 7 input = sys.stdin.readline8 from collections import deque9 10 n, m = map(int, input().split())11 12 13 14 graph = [[] for _ in range(n)]15 16 for _ in range(m):17 ai, bi = map(int, input().split())18 ai -= 119 bi -= 120 21 graph[ai].append(bi)22 23 inf = 10**1824 25 def bfs(vertex_count, graph, start_id):26 d = deque([start_id])27 visited = [False] * vertex_count28 dist = [inf] * vertex_count29 dist[start_id] = 030 31 while d:32 cur = d.pop()33 34 if visited[cur]:35 continue36 37 visited[cur] = True38 39 for to in graph[cur]:40 if visited[to]:41 continue42 43 d.append(to)44 dist[to] = min(dist[to], dist[cur] + 1)45 46 return visited, dist47 48 ans = list()49 50 for i in range(n):51 visited, dist = bfs(vertex_count=n, graph=graph, start_id=i)52 53 if dist.count(inf) == 0:54 ans.append(i + 1)55 56 57 if len(ans) == 1:58 print(*ans)59 else:60 print(-1)61 62 63if __name__ == "__main__":64 main()65