概要

この問題は、与えられた有向グラフ上を特定のルールに従って探索したとき、最終的に一度も訪れなかった部屋を特定する問題です。探索の挙動は深さ優先探索（DFS）に非常に酷似しており、ルールの通りに正しくシミュレーションを行うことで解くことができます。

考察

ルールの整理

問題文のルールを整理すると、以下のようになります。 - 現在の部屋 \(u\) から出る通路（辺）を、優先度順に 1 つずつ確認する。 - 通路の先にある部屋 \(v\) について： - すでに訪問済みなら、スキップする。 - 未訪問だが、照明の色が同じ（\(C_u = C_v\)）なら、スキップする。 - 未訪問で、照明の色が異なる（\(C_u \neq C_v\)）なら、部屋 \(v\) を訪問済みにして \(v\) へ移動する。 - すべての通路を確認しても移動先がない場合、直前にいた部屋に戻る（バックトラック）。 - バックトラックした際、「中断していた通路の確認を、中断した箇所の次の通路から再開する」。

高速化の鍵：「確認の再開」

素朴にシミュレーションを行う際、バックトラックして戻ってきたときに「その部屋から出る通路を最初からスキャンし直す」という実装をしてしまうと、同じ通路を何度も無駄に確認することになり、最悪の場合に実行時間制限（TLE）となってしまいます。

しかし、ルール 4 にある「中断した箇所の次の通路から再開する」という記述に注目すると、各部屋から出る通路は、探索全体を通してそれぞれ高々 1 回しか確認されないことが分かります。 したがって、各部屋 \(u\) について「次に確認すべき通路のインデックス」を保持しておき、一度確認した通路は二度と確認しないようにポインタを進めていくことで、無駄な重複走査を避けることができます。

これは、通常の DFS やオイラー路を求めるアルゴリズムなどで使われる「辺の走査ポインタを戻さない」テクニックと同じです。これを用いることで、全体の探索を \(O(N + M)\) の線形時間で行うことができます。

アルゴリズム

スタックを用いた非再帰の深さ優先探索（DFS）により、探索をシミュレーションします。

1. 初期化:

   • 各部屋が訪問済みかどうかを記録する配列 visited を用意し、すべて False で初期化します。ただし、部屋 \(1\) は開始時に訪問済み（True）とします。
   • 各部屋 \(u\) について、次に確認すべき通路のインデックスを記録する配列 edge_idx を \(0\) で初期化します。
   • 現在の探索経路（通ってきた部屋の履歴）を管理するスタック stack を用意し、初期状態として [1] を入れます。

2. シミュレーション: stack が空になるまで、以下の処理を繰り返します。

   • スタックの末尾にある要素（現在の部屋 \(u\)）を取得します（pop はせず、見るだけ）。
   • \(u\) から出る通路のリスト adj[u] において、現在指しているインデックス edge_idx[u] がリストのサイズ未満である場合：
     • 通路の先の部屋 \(v = \text{adj}[u][\text{edge\_idx}[u]]\) を取得し、edge_idx[u] を \(1\) 進めます。
     • \(v\) がすでに訪問済み、または \(C_u = C_v\) であれば、何もせず次のループへ進みます（スキップ）。
     • \(C_u \neq C_v\) であれば、\(v\) を訪問済み（visited[v] = True）にし、スタックに \(v\) を追加（stack.append(v)）して、次の部屋 \(v\) の探索へ移行します。
   • edge_idx[u] が通路のサイズに達している（探索し尽くした）場合：
     • スタックから \(u\) を取り除きます（stack.pop()）。これにより、直前にいた部屋（スタックの新たな末尾）にバックトラックします。

3. 出力:

   • 探索終了後、visited が False のままの部屋を小さい順に集め、存在すればそれらを出力し、存在しなければ COMPLETE と出力します。

計算量

• 時間計算量: \(O(N + M)\) 各部屋はスタックに高々 \(1\) 回しか追加されず、各通路も edge_idx によって高々 \(1\) 回しか評価されません。よって、グラフの規模に対して線形時間で動作します。
• 空間計算量: \(O(N + M)\) グラフを表現する隣接リスト adj に \(O(N + M)\)、スタックや訪問状態の管理に \(O(N)\) のメモリを使用します。

実装のポイント

• 非再帰（スタック）による実装: Python などの言語では、再帰関数を用いて DFS を実装すると、再帰の深さ制限（デフォルトでは \(1000\) 程度）に達してランタイムエラー（RecursionError）になることがあります。また、再帰呼び出しのオーバーヘッドも無視できません。 今回のようにスタックを用いたループによるシミュレーションを行うことで、再帰制限を気にする必要がなくなり、高速かつ安全に動作させることができます。

• edge_idx による状態管理: edge_idx[u] を用いて「どこまで通路を調べたか」を部屋ごとに独立して保持することが、この問題を \(O(N + M)\) で解くための最も重要なポイントです。

  ソースコード

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()

---

この解説は gemini-3.5-flash-thinking によって生成されました。