Overview

This problem asks you to determine which rooms are never visited when exploring a given directed graph according to specific rules. The exploration behavior is very similar to Depth-First Search (DFS), and the problem can be solved by correctly simulating the rules as described.

Analysis

Organizing the Rules

Organizing the rules from the problem statement, we get the following: - From the current room \(u\), check the passages (edges) going out one by one in priority order. - For the room \(v\) at the end of a passage: - If it has already been visited, skip it. - If it has not been visited but the lighting color is the same (\(C_u = C_v\)), skip it. - If it has not been visited and the lighting color is different (\(C_u \neq C_v\)), mark room \(v\) as visited and move to \(v\). - If no destination is found after checking all passages, return to the room you were in immediately before (backtrack). - When backtracking, “resume checking passages from the one after where you left off.”

Key to Optimization: “Resuming the Check”

When performing a naive simulation, if you “rescan all passages from the beginning” when backtracking to a room, you end up redundantly checking the same passages multiple times, which can result in a Time Limit Exceeded (TLE) in the worst case.

However, paying attention to Rule 4’s description of “resume from the passage after where you left off,” we can see that each passage from each room is checked at most once throughout the entire exploration. Therefore, by maintaining “the index of the next passage to check” for each room \(u\) and advancing the pointer so that a passage once checked is never checked again, we can avoid redundant scanning.

This is the same technique as “never resetting the edge scanning pointer,” used in standard DFS and Eulerian path algorithms. Using this technique, the entire exploration can be performed in \(O(N + M)\) linear time.

Algorithm

We simulate the exploration using a non-recursive depth-first search (DFS) with a stack.

1. Initialization:

   • Prepare an array visited to record whether each room has been visited, initialized to all False. However, room \(1\) is marked as visited (True) at the start.
   • Initialize an array edge_idx to \(0\) for each room \(u\), recording the index of the next passage to check.
   • Prepare a stack stack to manage the current exploration path (history of rooms traversed), initially containing [1].

2. Simulation: Repeat the following process until stack becomes empty:

   • Get the element at the top of the stack (current room \(u\)) (just peek, do not pop).
   • If the current index edge_idx[u] is less than the size of the passage list adj[u] from \(u\):
     • Get the room at the end of the passage \(v = \text{adj}[u][\text{edge\_idx}[u]]\), and increment edge_idx[u] by \(1\).
     • If \(v\) has already been visited, or \(C_u = C_v\), do nothing and proceed to the next loop iteration (skip).
     • If \(C_u \neq C_v\), mark \(v\) as visited (visited[v] = True), push \(v\) onto the stack (stack.append(v)), and transition to exploring the next room \(v\).
   • If edge_idx[u] has reached the size of the passage list (all passages have been exhausted):
     • Remove \(u\) from the stack (stack.pop()). This backtracks to the room you were in immediately before (the new top of the stack).

3. Output:

   • After the exploration ends, collect the rooms where visited is still False in ascending order. If any exist, output them; otherwise, output COMPLETE.

Complexity

• Time Complexity: \(O(N + M)\) Each room is added to the stack at most once, and each passage is evaluated at most once due to edge_idx. Therefore, it runs in linear time with respect to the size of the graph.
• Space Complexity: \(O(N + M)\) The adjacency list adj representing the graph uses \(O(N + M)\), and the stack and visited state management use \(O(N)\) memory.

Implementation Notes

• Non-recursive (stack-based) implementation: In languages like Python, implementing DFS using recursive functions can hit the recursion depth limit (around \(1000\) by default) and cause a runtime error (RecursionError). The overhead of recursive calls is also non-negligible. By performing the simulation using a loop with a stack as in this approach, you don’t need to worry about recursion limits, and the code runs quickly and safely.

• State management with edge_idx: Using edge_idx[u] to independently maintain “how far passages have been checked” for each room is the most important point for solving this problem in \(O(N + M)\).

  Source Code

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各部屋の照明の色（1-indexed）
    C = [0] + [int(x) for x in input_data[2:2+N]]
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    idx = 2 + N
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        adj[u].append(v)
        idx += 2
        
    # 探索用配列
    visited = [False] * (N + 1)
    visited[1] = True
    stack = [1]
    edge_idx = [0] * (N + 1)
    
    # DFSシミュレーション
    while stack:
        u = stack[-1]
        u_edges = adj[u]
        if edge_idx[u] < len(u_edges):
            v = u_edges[edge_idx[u]]
            edge_idx[u] += 1
            if visited[v]:
                continue
            if C[v] == C[u]:
                continue
            visited[v] = True
            stack.append(v)
        else:
            stack.pop()
            
    # 一度も訪れなかった部屋の抽出
    unvisited = [i for i in range(1, N + 1) if not visited[i]]
    
    if not unvisited:
        print("COMPLETE")
    else:
        print(*(unvisited))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.5-flash-thinking.