No Escape
You are a systems engineer at Blizzard working on a new MMO dungeon. Some room clusters form inescapable loops — once a player enters any room in the cluster, they can only exit by clearing every room in it. These are called encounter locks.
Formally, a group of rooms forms an encounter lock if every room in the group is reachable from every other room in the group. Find all such groups.
Given n rooms numbered 0 to n-1 and directed connections between rooms, return all Strongly Connected Components (SCCs). Each SCC should be returned as a sorted list of room indices. The outer list should be sorted by the smallest element in each SCC.
Example 1
(4, [[0,1],[1,2],[2,3],[3,0]])[[0, 1, 2, 3]]All 4 rooms form one giant loop — every room leads back to every other room. One massive encounter lock.
Example 2
(5, [[0,1],[1,0],[3,4],[4,3]])[[0, 1], [2], [3, 4]]Rooms 0 and 1 form a loop. Rooms 3 and 4 form a loop. Room 2 has no connections — it is its own trivial SCC.
Example 3
(3, [[0,1],[0,2],[2,1]])[[0], [1], [2]]No cycles exist — the edge 2→1 is a cross-edge, not a back-edge. Every room is its own SCC. Critical: the on_stack check distinguishes back-edges from cross-edges.
- ›1 <= n <= 1000
- ›0 <= len(edges) <= 5000
- ›No self-loops
Loading question…