概要

有向グラフ上で、負荷（入次数）が耐久値を超えた変電所が停電し、その停電が連鎖的に広がっていくシミュレーション問題です。BFS（幅優先探索）を用いて連鎖停電を効率的にシミュレーションします。

考察

問題の構造を理解する

各変電所 \(i\) の初期負荷は「入次数」（自分に向かって入ってくる送電線の本数）です。負荷が耐久値 \(T_i\) を真に超えている変電所は停電を起こします。

停電を起こした変電所 \(s\) からの出力辺（\(s\) から出ていく送電線）の先にある変電所の負荷が \(1\) ずつ増えます。これは「\(s\) からの電力供給が途絶えたため、送電先が他から補おうとして負荷が増大する」というモデルです。

重要な気づき

• 停電の連鎖はドミノ倒しのような構造です。一つの停電が周囲の負荷を増やし、新たな停電を誘発します。
• 問題文に「どの順番で処理しても最終結果は同じ」と保証されています。これにより、BFS のようなキューベースの処理で正しい結果が得られます。
• 素朴に「毎回全変電所を走査して条件を満たすものを探す」と \(O(N^2)\) になりかねませんが、キューを使えば各変電所を高々1回しか処理しないため効率的です。

具体例で理解する

例えば、変電所 \(A \to B \to C\) という送電線があり、\(B\) の入次数が \(1\)、耐久値が \(0\) だとします。

1. \(B\) の初期負荷は \(1 > 0 = T_B\) なので停電
2. \(B\) から \(C\) への送電線があるため、\(C\) の負荷が \(+1\)
3. \(C\) の負荷が耐久値を超えていれば \(C\) も停電…と連鎖

アルゴリズム

1. 初期化: 各変電所の入次数を計算し、それを初期負荷とする。
2. 初期キュー投入: 負荷 \(>\) 耐久値 の変電所をすべてキューに入れ、停電フラグを立てる。
3. BFS ループ:
   • キューから変電所 \(s\) を取り出す。
   • \(s\) の出力辺をすべて調べ、送電先 \(v\) がまだ停電していなければ \(v\) の負荷を \(+1\) する。
   • 負荷が耐久値を超えた \(v\) は停電フラグを立ててキューに追加。
4. 出力: キューが空になったら、停電した変電所を昇順に出力。なければ -1 を出力。

ポイントは、停電フラグを立てるのはキューに入れるタイミングであることです。これにより同じ変電所を二重にキューに入れることを防ぎます。

計算量

• 時間計算量: \(O(N + M)\)
  • 各変電所は高々1回キューに入り、各送電線は停電元の変電所が処理されるときに高々1回走査されます。
• 空間計算量: \(O(N + M)\)
  • 隣接リスト、負荷配列、停電フラグ配列などに必要です。

実装のポイント

• 入力の高速読み込み: \(N, M\) が最大 \(2 \times 10^5\) のため、Python では sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 停電フラグの管理: キューに追加する時点で blacked_out[v] = True とすることで、同じ変電所が複数回キューに入ることを防ぎます。負荷が増加するたびにキューに入れてしまうと無駄な処理が発生します。

• 負荷の不変性: 問題文に「一度停電を起こした変電所の負荷はその後変化しない」とあるため、blacked_out[v] が True の変電所に対しては負荷を増やさないようにします。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    T = [0] * (N + 1)
    for i in range(1, N + 1):
        T[i] = int(input_data[idx]); idx += 1
    
    # out_edges[u] = list of v such that there's an edge u -> v
    out_edges = [[] for _ in range(N + 1)]
    in_degree = [0] * (N + 1)
    
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        out_edges[u].append(v)
        in_degree[v] += 1
    
    # load[i] starts as in_degree[i]
    load = [0] * (N + 1)
    for i in range(1, N + 1):
        load[i] = in_degree[i]
    
    # BFS/queue-based simulation
    blacked_out = [False] * (N + 1)
    queue = deque()
    
    for i in range(1, N + 1):
        if load[i] > T[i]:
            queue.append(i)
            blacked_out[i] = True
    
    result = []
    
    while queue:
        s = queue.popleft()
        result.append(s)
        # For each outgoing edge from s
        for v in out_edges[s]:
            if not blacked_out[v]:
                load[v] += 1
                if load[v] > T[v]:
                    blacked_out[v] = True
                    queue.append(v)
    
    if not result:
        print(-1)
    else:
        result.sort()
        print(' '.join(map(str, result)))

main()

---

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