結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー gew1fw
提出日時 2025-06-12 19:55:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,400 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 127,116 KB
最終ジャッジ日時 2025-06-12 19:55:46
合計ジャッジ時間 4,828 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    edges = []
    for _ in range(M):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        edges.append((u, v))
    
    # Compute connected components using DSU
    parent = list(range(N + 1))
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    def union(u, v):
        pu = find(u)
        pv = find(v)
        if pu != pv:
            parent[pv] = pu
    for u, v in edges:
        union(u, v)
    
    # Count number of connected components
    components = set()
    for i in range(1, N + 1):
        components.add(find(i))
    C = len(components)
    
    # Compute in and out degrees
    in_degree = [0] * (N + 1)
    out_degree = [0] * (N + 1)
    for u, v in edges:
        out_degree[u] += 1
        in_degree[v] += 1
    
    # Compute sum_plus
    sum_plus = 0
    for v in range(1, N + 1):
        delta = out_degree[v] - in_degree[v]
        if delta > 0:
            sum_plus += delta
    
    # Compute required K
    K1 = max(sum_plus - 1, 0)
    K2 = max(C - 1, 0)
    K = max(K1, K2)
    
    print(K)

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