概要

有向グラフ上の強連結成分（SCC）を求め、各SCCに対して必要な操作回数を計算する問題です。サイズ1のSCCに属するノードはレベルを上げられないため不可能判定が必要で、サイズ2以上のSCCはまとめてレベルが上がるため、SCC内の最大不足分が必要操作回数になります。

考察

重要な気づき①：操作の対象は強連結成分

サーバー \(v\) を選んだときの \(S(v)\) は「\(v\) から到達可能かつ \(v\) へも到達可能なサーバーの集合」です。これはグラフ理論における \(v\) を含む強連結成分（SCC）そのものです。ただし、\(v\) が閉路上にない場合（自分自身に戻れない場合）は \(S(v) = \emptyset\) です。

重要な気づき②：サイズ1のSCCは操作不能

問題文より自己ループ（\(U_i = V_i\)）は存在しません。したがって、サイズ1のSCCに属するノード \(v\) は閉路上にないため、\(S(v) = \emptyset\) となり、どう操作しても \(W_v\) を増やせません。もし \(T_v > W_v\) なら答えは -1 です。

重要な気づき③：サイズ2以上のSCCは一括で+1される

サイズ2以上のSCC内のどのノード \(v\) を選んでも、\(S(v)\) はそのSCC全体と一致し、SCC内の全ノードのレベルが一律に1増えます。したがって、そのSCCに必要な操作回数は：

\[\max(0, \max_{j \in \text{SCC}} (T_j - W_j))\]

具体例

サーバー3台が互いに到達可能（1つのSCC）で、各不足分が \((T_j - W_j) = 3, 5, 2\) のとき、5回操作すればすべて基準達成します。

アルゴリズム

1. SCC分解：Kosarajuのアルゴリズムで有向グラフの強連結成分を求める。
2. 不可能判定：サイズ1のSCCに属するノード \(j\) について \(T_j > W_j\) なら -1 を出力。
3. 操作回数計算：サイズ2以上の各SCCについて、\(\max(0, \max_{j \in \text{SCC}}(T_j - W_j))\) を計算し、全SCCの合計を求める。

Kosarajuのアルゴリズムは以下の2パスで構成されます： - 第1パス：元のグラフ上でDFSし、帰りがけ順（finish order）を記録。 - 第2パス：逆グラフ上で、帰りがけ順の逆順にDFS/BFSし、各連結成分を特定。

計算量

• 時間計算量: \(O(N + M)\)（SCC分解が \(O(N+M)\)、各ノードの判定が \(O(N)\)）
• 空間計算量: \(O(N + M)\)（グラフ・逆グラフ・SCC情報の格納）

実装のポイント

• 再帰ではなく反復DFS：\(N\) が最大 \(2 \times 10^5\) のため、Pythonの再帰制限に引っかからないよう、スタックを使った反復DFSで帰りがけ順を求めます。

• 自己ループが存在しない制約の活用：サイズ1のSCCは必ず閉路を持たないので、単純にSCCサイズで場合分けできます。

• 64bit整数：不足分の合計が大きくなる可能性がありますが、Pythonでは整数のオーバーフローがないため特別な対応は不要です。

  ソースコード

import sys
from sys import setrecursionlimit

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
    
    W = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    T = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    graph = [[] for _ in range(N)]
    rgraph = [[] for _ in range(N)]
    
    for i in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        graph[u].append(v)
        rgraph[v].append(u)
    
    # Kosaraju's algorithm for SCC
    # Step 1: Get finish order
    order = []
    visited = [False] * N
    
    # Iterative DFS for finish order
    for s in range(N):
        if visited[s]:
            continue
        stack = [(s, 0)]
        visited[s] = True
        while stack:
            node, idx_child = stack[-1]
            if idx_child < len(graph[node]):
                stack[-1] = (node, idx_child + 1)
                nxt = graph[node][idx_child]
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append((nxt, 0))
            else:
                stack.pop()
                order.append(node)
    
    # Step 2: Assign components in reverse finish order
    comp = [-1] * N
    num_comp = 0
    for s in reversed(order):
        if comp[s] != -1:
            continue
        # BFS/DFS on reverse graph
        c = num_comp
        num_comp += 1
        queue = [s]
        comp[s] = c
        head = 0
        while head < len(queue):
            node = queue[head]
            head += 1
            for nxt in rgraph[node]:
                if comp[nxt] == -1:
                    comp[nxt] = c
                    queue.append(nxt)
    
    # Build SCC info
    scc_size = [0] * num_comp
    for i in range(N):
        scc_size[comp[i]] += 1
    
    # For each SCC, compute the required number of operations
    # An SCC with size 1 and no self-loop: cannot be incremented (S(v) is empty)
    # An SCC with size >= 2, or size 1 with self-loop: can be incremented
    
    # Check which size-1 SCCs have a self-loop
    # Actually, problem says no self-loops (U_i != V_i), so size-1 SCCs never have a cycle
    # Wait, a size-1 SCC can still be part of a cycle if there's a self-loop, but the problem
    # states U_i != V_i, so no self-loops exist. A size-1 SCC with no self-loop means
    # the node is NOT on any cycle, so S(v) = empty.
    
    # For SCC of size >= 2: all nodes are on a cycle (they can reach each other)
    # For SCC of size 1: the single node is NOT on any cycle (no self-loop possible)
    
    # So for size-1 SCCs: the node cannot be incremented at all.
    #   If T[node] > W[node], it's impossible -> return -1
    # For size >= 2 SCCs: one operation on any node in the SCC increments ALL nodes in SCC by 1
    #   Required operations = max(0, max over nodes in SCC of (T[node] - W[node]))
    
    # Compute per-SCC required increments
    scc_need = [0] * num_comp
    
    for i in range(N):
        c = comp[i]
        diff = T[i] - W[i]
        if diff > 0:
            if scc_size[c] == 1:
                # Cannot increment this node
                print(-1)
                return
            else:
                if diff > scc_need[c]:
                    scc_need[c] = diff
    
    total = sum(scc_need)
    print(total)

if __name__ == '__main__':
    main()

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