概要

有向グラフで表される電力網において、変電所の負荷が耐久値を超えると停電が連鎖的に広がる現象をシミュレーションする問題です。

考察

初期状態では、各変電所の負荷はその変電所への入次数（流入する送電線の本数）に等しいです。停電が発生すると、その変電所から出ている送電線の先にある変電所の負荷が1ずつ増加します。この増加によって他の変電所の負荷が耐久値を超えると、さらに停電が連鎖します。

重要な観察点は、停電の連鎖が「幅優先探索（BFS）」のように広がることです。一度停電した変電所は再び処理する必要がなく、各変電所は最大1回しか停電しないため、効率的なシミュレーションが可能です。

素朴なアプローチとして、毎回すべての変電所をチェックして停電条件を満たすものを探す方法が考えられますが、これでは最悪ケースで \(O(N^2)\) の時間がかかり、制約条件 \(N \leq 2 \times 10^5\) では実行時間が超過します。

アルゴリズム

1. 初期化: 各変電所の初期負荷（入次数）と耐久値を記録します。
2. キュー初期化: 初期状態で停電条件（負荷 \(>\) 耐久値）を満たす変電所をすべてキューに追加し、停電済みとマークします。
3. BFSによるシミュレーション: キューが空になるまで以下を繰り返します：
   • キューから変電所を取り出し、その変電所から出ているすべての送電線を処理します
   • 送電先の変電所がまだ停電していない場合、その負荷を1増加させます
   • 増加後の負荷が耐久値を超えた場合、その変電所をキューに追加し、停電済みとマークします
4. 結果出力: 最終的に停電した変電所の番号を昇順で出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 各変電所と各送電線は高々1回ずつ処理されます
• 空間計算量: \(O(N + M)\)
  • グラフの表現に \(O(N + M)\)、各種配列に \(O(N)\) のメモリを使用します

実装のポイント

• グラフを隣接リストで表現することで効率的な探索を実現します

• 停電済みかどうかを管理する stopped 配列を使用し、重複処理を防ぎます

• キューを使用することで、停電の連鎖を自然な順序でシミュレーションできます

• 入力データが空の場合の処理（-1出力）を忘れずに実装します

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    T = [0] * (n+1)
    for i in range(1, n+1):
        T[i] = int(next(it))
        
    graph = [[] for _ in range(n+1)]
    in_deg = [0] * (n+1)
    
    for _ in range(m):
        u = int(next(it)); v = int(next(it))
        graph[u].append(v)
        in_deg[v] += 1
        
    initial_load = in_deg[:]
    current_load = initial_load[:]
    
    stopped = [False] * (n+1)
    q = deque()
    
    for i in range(1, n+1):
        if current_load[i] > T[i]:
            q.append(i)
            stopped[i] = True
            
    while q:
        s = q.popleft()
        for neighbor in graph[s]:
            if not stopped[neighbor]:
                current_load[neighbor] += 1
                if current_load[neighbor] > T[neighbor]:
                    stopped[neighbor] = True
                    q.append(neighbor)
                    
    result = []
    for i in range(1, n+1):
        if stopped[i]:
            result.append(i)
            
    if not result:
        print(-1)
    else:
        print(" ".join(map(str, result)))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。