結果

問題 No.1813 Magical Stones
ユーザー lam6er
提出日時 2025-03-20 21:12:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 582 ms / 2,000 ms
コード長 2,597 bytes
コンパイル時間 468 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 127,476 KB
最終ジャッジ日時 2025-03-20 21:13:53
合計ジャッジ時間 13,079 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, stdin.readline().split())
    edges = [[] for _ in range(n + 1)]
    reverse_edges = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        edges[a].append(b)
        reverse_edges[b].append(a)

    # Kosaraju's algorithm to find SCC
    visited = [False] * (n + 1)
    order = []

    # First pass to get the order
    for u in range(1, n + 1):
        if not visited[u]:
            stack = [(u, False)]
            while stack:
                node, processed = stack.pop()
                if processed:
                    order.append(node)
                    continue
                if visited[node]:
                    continue
                visited[node] = True
                stack.append((node, True))
                for v in edges[node]:
                    if not visited[v]:
                        stack.append((v, False))
    
    # Second pass to get SCCs
    visited = [False] * (n + 1)
    scc = []
    scc_id = [0] * (n + 1)
    for u in reversed(order):
        if not visited[u]:
            current_scc = []
            stack = [u]
            visited[u] = True
            current_scc.append(u)
            while stack:
                node = stack.pop()
                for v in reverse_edges[node]:
                    if not visited[v]:
                        visited[v] = True
                        current_scc.append(v)
                        stack.append(v)
            scc.append(current_scc)
    
    # Assign scc id to each node
    for i in range(len(scc)):
        for node in scc[i]:
            scc_id[node] = i
    
    # Build DAG edges
    existing_edges = set()
    dag_edges = defaultdict(set)
    for a in range(1, n + 1):
        scc_a = scc_id[a]
        for b in edges[a]:
            scc_b = scc_id[b]
            if scc_a != scc_b and (scc_a, scc_b) not in existing_edges:
                existing_edges.add((scc_a, scc_b))
                dag_edges[scc_a].add(scc_b)
    
    # Compute in_degree and out_degree for each SCC in DAG
    k = len(scc)
    if k == 1:
        print(0)
        return
    
    in_degree = [0] * k
    out_degree = [0] * k
    
    for u in dag_edges:
        for v in dag_edges[u]:
            out_degree[u] += 1
            in_degree[v] += 1
    
    a = sum(1 for i in range(k) if in_degree[i] == 0)
    b = sum(1 for i in range(k) if out_degree[i] == 0)
    
    print(max(a, b))

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