概要

洞窟の部屋をルールに従って探検するシミュレーション問題。深さ優先探索（DFS）の変種で、移動条件として「行き先の部屋の照明の色が現在の部屋と異なること」が加わっている。

考察

問題の本質

この問題は、通常のDFS（深さ優先探索）に以下の特殊ルールが追加されたものです： - 移動できる条件: 行き先が未訪問 かつ 照明の色が現在の部屋と異なること - 同色スキップ: 行き先が未訪問でも同色なら移動しない。ただし訪問済みにもしない（将来別ルートから訪問される可能性がある） - バックトラック後の再開: 戻ってきたら、中断した次の通路から確認を再開する

重要な気づき

バックトラック後に「中断した箇所の次の通路から」再開するという点が重要です。つまり、各部屋の通路リストは一度通過した部分を再度確認しない構造になっています。これにより、各辺は高々1回しか確認されず、効率的にシミュレーションできます。

素朴な再帰では？

再帰で実装すると、\(N\) が最大 \(2 \times 10^5\) のためスタックオーバーフローの危険があります。反復的（スタックを自前で管理する）実装が必要です。

アルゴリズム

スタックを用いた反復的DFSで探検をシミュレーションします。

1. スタックに (部屋番号, 次に確認する辺のインデックス) を積む
2. スタックの先頭の部屋について、辺インデックスから順に通路を確認：
   • 行き先が訪問済み → スキップ（インデックスを進める）
   • 行き先が未訪問で同色 → スキップ（インデックスを進める、訪問済みにしない）
   • 行き先が未訪問で異色 → 訪問済みにして移動（スタックに新しい部屋を積む）
3. すべての通路を確認しても移動先がなければ、スタックからポップ（バックトラック）
4. スタックが空になったら探検終了

具体例（\(N=4\), 部屋1:赤, 部屋2:青, 部屋3:赤, 部屋4:青, 辺: 1→3, 1→2, 2→4）： - 部屋1（赤）: 通路1→3を確認 → 部屋3は赤（同色）→ スキップ - 部屋1（赤）: 通路1→2を確認 → 部屋2は青（異色）→ 移動！ - 部屋2（青）: 通路2→4を確認 → 部屋4は青（同色）→ スキップ - 部屋2: 通路なし → バックトラックで部屋1に戻る - 部屋1: 通路1→2の次から再開 → もう通路なし → 探検終了 - 未訪問: 部屋3, 部屋4

計算量

• 時間計算量: \(O(N + M)\)
  • 各辺は高々1回だけ確認される（バックトラック後は中断箇所の次から再開するため、辺のインデックスは戻らない）
• 空間計算量: \(O(N + M)\)
  • 隣接リストに \(O(N + M)\)、スタックに最大 \(O(N)\)

実装のポイント

• スタックの各要素に辺インデックスを保持: stack[-1] = (room, ei) のように更新することで、バックトラック後に正しい位置から再開できる

• 再帰ではなく反復: Pythonのデフォルト再帰上限を回避し、大きな入力にも対応

• visited[v] のチェックタイミング: 問題文の「その時点での状態で判定」に対応して、辺を確認するたびにリアルタイムで visited 配列を参照する

• 同色スキップ時に ei を進める: 同色の未訪問部屋はスキップするが訪問済みにしないため、別の部屋からの探索で後から訪問される可能性がある。ただし現在の部屋からはもう確認しない（インデックスが進んでいるため）

  ソースコード

import sys
from sys import setrecursionlimit

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    M = int(tokens[idx]); idx += 1
    
    C = [0] * (N + 1)
    for i in range(1, N + 1):
        C[i] = int(tokens[idx]); idx += 1
    
    # adj[u] = list of v in order of priority (first given = highest priority)
    adj = [[] for _ in range(N + 1)]
    for j in range(M):
        u = int(tokens[idx]); idx += 1
        v = int(tokens[idx]); idx += 1
        adj[u].append(v)
    
    visited = [False] * (N + 1)
    visited[1] = True
    
    # Iterative DFS simulation
    # Stack stores (room, edge_index)
    # For each room on the stack, we process edges starting from edge_index
    
    stack = [(1, 0)]
    
    while stack:
        room, ei = stack[-1]
        edges = adj[room]
        moved = False
        
        while ei < len(edges):
            v = edges[ei]
            ei += 1  # next edge index for when we resume
            
            if visited[v]:
                # skip visited
                continue
            
            # v is unvisited
            if C[v] == C[room]:
                # same color, skip but don't mark visited
                continue
            else:
                # different color, move to v
                visited[v] = True
                # Update current frame's edge index before pushing new frame
                stack[-1] = (room, ei)
                stack.append((v, 0))
                moved = True
                break
        
        if not moved:
            # All edges exhausted, backtrack
            stack.pop()
    
    unvisited = [i for i in range(1, N + 1) if not visited[i]]
    
    if not unvisited:
        print("COMPLETE")
    else:
        print(' '.join(map(str, unvisited)))

main()

この解説は claude4.6opus-thinking によって生成されました。