Day 073-Q2 — SCC + DAG 上の最長重み付きパス

問題

$N$ 頂点 $M$ 辺の有向グラフ $G$ が与えられる。各頂点 $v$ には価値 $a_v$ が設定されている（負の値もあり得る）。

強連結成分（SCC）内の頂点価値の総和を SCC の価値とする。縮退グラフ上で、価値の和が最大になる経路を求めよ。

すなわち、頂点の部分列 $v_1 \to v_2 \to \cdots \to v_k$（元グラフの辺が存在）で $\sum_{i=1}^{k} a_{v_i}$ の最大値を答えよ。同一 SCC 内の頂点は SCC の価値としてまとめて計算する。

入出力例

5 5
3 -1 4 -1 5
1 2
2 3
3 1
1 4
4 5

10

概念図: 縮退グラフ（Condensation Graph）

ヒント

dp = [scc_val[i] for i in range(c)]
for cu in topo:
    for cv in dag[cu]:
        dp[cv] = max(dp[cv], dp[cu] + scc_val[cv])
print(max(dp))

模範解答

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))

    graph  = defaultdict(list)
    rgraph = defaultdict(list)
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        graph[u].append(v)
        rgraph[v].append(u)

    # Kosaraju SCC (反復 DFS)
    visited = [False] * N
    order = []
    for start in range(N):
        if not visited[start]:
            stack = [(start, iter(graph[start]))]
            visited[start] = True
            while stack:
                node, it = stack[-1]
                try:
                    nxt = next(it)
                    if not visited[nxt]:
                        visited[nxt] = True
                        stack.append((nxt, iter(graph[nxt])))
                except StopIteration:
                    order.append(node)
                    stack.pop()

    comp = [-1] * N
    c = 0
    for v in reversed(order):
        if comp[v] != -1:
            continue
        stack = [v]
        comp[v] = c
        while stack:
            node = stack.pop()
            for nxt in rgraph[node]:
                if comp[nxt] == -1:
                    comp[nxt] = c
                    stack.append(nxt)
        c += 1

    # SCC 価値計算
    scc_val = [0] * c
    for i in range(N):
        scc_val[comp[i]] += a[i]

    # 縮退 DAG 構築
    dag = defaultdict(set)
    for u in range(N):
        for v in graph[u]:
            cu, cv = comp[u], comp[v]
            if cu != cv:
                dag[cu].add(cv)

    # トポロジカルソート (Kahn 法)
    in_deg = [0] * c
    for cu in dag:
        for cv in dag[cu]:
            in_deg[cv] += 1

    queue = deque(i for i in range(c) if in_deg[i] == 0)
    topo = []
    while queue:
        node = queue.popleft()
        topo.append(node)
        for nxt in dag[node]:
            in_deg[nxt] -= 1
            if in_deg[nxt] == 0:
                queue.append(nxt)

    # DAG 上 DP
    dp = [scc_val[i] for i in range(c)]
    for cu in topo:
        for cv in dag[cu]:
            dp[cv] = max(dp[cv], dp[cu] + scc_val[cv])

    print(max(dp))

solve()

Step-by-Step 解説

Step 1: Kosaraju 法で SCC 分解

1回目の DFS（元グラフ）: 全頂点の DFS 完了順を記録。2回目の DFS（逆グラフ）: 完了順の逆から未訪問頂点に DFS → 同一ツリーが同一 SCC。計算量 $O(N+M)$。

Step 2: SCC の価値計算

各頂点 $v$ が属する SCC $c$ の価値に $a_v$ を加算。SCC 内の頂点は循環可能なので全頂点を経由できる。

Step 3: 縮退 DAG の構築

元グラフの辺 $(u, v)$ で $\text{comp}[u] \ne \text{comp}[v]$ なものを DAG の辺として追加。セットで重複除去。

Step 4: DAG 上の最長パス DP

初期値: $dp[c] = \text{val}[c]$。遷移: トポソート順に $dp[cv] = \max(dp[cv], dp[cu] + \text{val}[cv])$。答え: $\max_c dp[c]$。

よくあるミス

次のステップ

• 発展: 縮退 DAG 上でパスの数え上げ（トポソート + DP）
• 発展: SCC 内に辺コストがある場合の最長パス
• 発展: DAG 上の最短パス（負コスト許容）

自己評価