結果

問題 No.1194 Replace
ユーザー gew1fw
提出日時 2025-06-12 15:18:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,757 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 315,828 KB
最終ジャッジ日時 2025-06-12 15:18:28
合計ジャッジ時間 7,073 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, sys.stdin.readline().split())
    operations = []
    nodes = set()
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().split())
        operations.append((b, c))
        nodes.add(b)
        nodes.add(c)
    nodes = list(nodes)
    node_set = set(nodes)
    graph = defaultdict(list)
    reverse_graph = defaultdict(list)
    for b, c in operations:
        graph[b].append(c)
        reverse_graph[c].append(b)
    visited = set()
    order = []
    def dfs(u):
        stack = [(u, False)]
        while stack:
            node, processed = stack.pop()
            if processed:
                order.append(node)
                continue
            if node in visited:
                continue
            visited.add(node)
            stack.append((node, True))
            for v in graph.get(node, []):
                if v not in visited:
                    stack.append((v, False))
    for u in nodes:
        if u not in visited:
            dfs(u)
    visited = set()
    scc = []
    component = {}
    current = 0
    for u in reversed(order):
        if u not in visited:
            stack = [u]
            visited.add(u)
            members = []
            while stack:
                node = stack.pop()
                members.append(node)
                for v in reverse_graph.get(node, []):
                    if v not in visited:
                        visited.add(v)
                        stack.append(v)
            scc.append(members)
            for member in members:
                component[member] = current
            current += 1
    max_in_scc = [max(s) for s in scc]
    scc_edges = [[] for _ in range(len(scc))]
    edge_set = set()
    for u in nodes:
        for v in graph.get(u, []):
            if component[u] != component[v] and (component[u], component[v]) not in edge_set:
                scc_edges[component[u]].append(component[v])
                edge_set.add((component[u], component[v]))
    sc_list = sorted(enumerate(max_in_scc), key=lambda x: -x[1])
    component_max = [0] * len(scc)
    for i, _ in sc_list:
        component_max[i] = max_in_scc[i]
        for neighbor in scc_edges[i]:
            if component_max[neighbor] > component_max[i]:
                component_max[i] = component_max[neighbor]
    max_reachable = {}
    for idx, members in enumerate(scc):
        for member in members:
            max_reachable[member] = component_max[idx]
    total = 0
    for j in range(1, n+1):
        if j in max_reachable:
            total += max_reachable[j]
        else:
            total += j
    print(total)

if __name__ == "__main__":
    main()
0