概要

停電の連鎖をそのままシミュレーションする代わりに、「最終的に停電しない変電所集合」が満たすべき条件を式にして、条件を満たせない頂点をキューで削っていく（コア分解のような）方法で解きます。

考察

1. 負荷がどう変化するか

変電所 \(v\) の初期負荷は入次数 \(\mathrm{in}(v)\) です。
さらに、\(u \to v\) の送電線があるとき、\(u\) が停電すると（\(v\) がまだ生きていれば）\(v\) の負荷は \(+1\) されます。

つまり 生き残った 変電所 \(v\) の最終的な負荷は

• 初期分 \(\mathrm{in}(v)\)
  
• 停電した「入ってくる元」からの増加分（\(v\) の入辺のうち、出発点が停電したものの本数）

の和になります。

2. 「生き残り集合」で条件を書く（ここが核心）

最終的に停電しない集合を \(A\)（Alive）とします。\(v \in A\) について考えると、\(v\) への入辺は全部で \(\mathrm{in}(v)\) 本あり、そのうち

• 出発点も生存している入辺本数：\(\mathrm{in}_A(v)\)
• 出発点が停電した入辺本数：\(\mathrm{in}(v)-\mathrm{in}_A(v)\)

です。

\(A\) に残った \(v\) は、停電した入隣接点の分だけ負荷が増えるので、最終負荷は

[ \mathrm{in}(v) + \bigl(\mathrm{in}(v)-\mathrm{in}_A(v)\bigr) = 2\mathrm{in}(v)-\mathrm{in}_A(v) ]

生き残るには、連鎖が収まった時点で「負荷が耐久値を超えない」必要があるので

[ 2\mathrm{in}(v)-\mathrm{in}_A(v) \le T_v ]

これを変形すると

[ \mathrm{in}_A(v) \ge 2\mathrm{in}(v) - T_v ]

よって、各頂点 \(v\) には [ \text{need}(v)=\max(0,\;2\mathrm{in}(v)-T_v) ] という「生存するために、生存集合 \(A\) から入ってくる必要本数」が定まります。

具体例

\(\mathrm{in}(v)=3,\;T_v=4\) のとき
\(\text{need}(v)=2\cdot3-4=2\)。
「生存集合からの入辺が2本以上必要」＝「停電してよい入隣接点は高々1個」
初期負荷3から最大1だけ増えて4まで耐えられる、という直感と一致します。

3. 素朴にやると困ること

手順通りに「負荷 \(>T\) の頂点を選んで停電」を繰り返すと、毎回の選択や更新が必要です。
しかし上の考察により、最終状態は「生存集合 \(A\) が need 条件を満たすか」だけで判定でき、順序に依らず一意なので、直接 \(A\) を求める方が簡潔・高速になります。

アルゴリズム

求めたいのは、条件 [ \forall v\in A:\ \mathrm{in}_A(v)\ge \text{need}(v) ] を満たす最大の集合 \(A\)（条件を満たせないものを削っていった残り）です。

手順は次の「削除（peeling）」です。

1. 入次数 \(\mathrm{in}(v)\) を数える。
   
2. 各 \(v\) について \(\text{need}(v)=\max(0,2\mathrm{in}(v)-T_v)\) を計算する。
3. 現在残っている頂点から \(v\) へ入ってくる本数を in_remain[v] として管理する。初期は in_remain[v]=in(v)。
4. in_remain[v] < need[v] となった頂点 \(v\) は、もはや条件を満たせず生き残れないので削除候補としてキューに入れる。
5. キューから頂点 \(u\) を取り出して削除する。すると \(u\) は「生存集合から消える」ので、\(u\to w\) の各辺について \(w\) の in_remain[w] が 1 減る（\(u\) が \(w\) に与えていた「生存集合からの入辺」が1本減る）。
6. その結果 in_remain[w] < need[w] になったら \(w\) もキューに入れる。
7. キューが空になるまで繰り返す。

最後に削除された頂点が「最終的に停電する頂点集合」です（生存集合 \(A\) の補集合）。

コードでは、 - out[u]：\(u\) から出る先（隣接リスト） - in_remain[v]：現在残っている頂点から \(v\) に入る本数 - need[v]：生き残りに必要な本数 - removed[v]：削除（=停電確定）済みか

を使って上記を実装しています。

計算量

• 時間計算量: \(O(N+M)\)（各頂点は高々1回削除、各辺は高々1回 in_remain を減らす）
• 空間計算量: \(O(N+M)\)（隣接リストと各種配列）

実装のポイント

• need[v]=2*indeg[v]-T[v] が負になる場合は \(0\) に丸めます（生存集合からの入辺が「負の本数必要」はありえないため）。

• 削除時は out[u] をたどって「行き先の in_remain を減らす」点に注意（\(u\) が消えると、\(u\) から出ていた辺が「生存集合からの入辺」として数えられなくなる）。

• 同じ頂点がキューに複数回入る可能性があるので、取り出したときに removed[u] をチェックして二重処理を防ぎます。

• 出力は削除された頂点（removed[i]==1）を昇順に。空なら -1。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    T = [next(it) for _ in range(N)]

    out = [[] for _ in range(N)]
    indeg = [0] * N
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        out[u].append(v)
        indeg[v] += 1

    need = [0] * N
    in_remain = indeg[:]
    q = deque()
    for i in range(N):
        ni = 2 * indeg[i] - T[i]
        if ni < 0:
            ni = 0
        need[i] = ni
        if in_remain[i] < ni:
            q.append(i)

    removed = bytearray(N)
    while q:
        u = q.popleft()
        if removed[u]:
            continue
        removed[u] = 1
        for v in out[u]:
            if removed[v]:
                continue
            in_remain[v] -= 1
            if in_remain[v] < need[v]:
                q.append(v)

    ans = [str(i + 1) for i in range(N) if removed[i]]
    if not ans:
        sys.stdout.write("-1\n")
    else:
        sys.stdout.write(" ".join(ans) + "\n")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。