結果

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

ソースコード

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 in undirected graph
    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):
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent[v_root] = u_root
    for u, v in edges:
        union(u, v)
    # Count connected components
    visited = set()
    C = 0
    for v in range(1, N+1):
        root = find(v)
        if root not in visited:
            visited.add(root)
            C += 1
    
    # Compute D_v for each vertex
    out = [0] * (N + 1)
    in_ = [0] * (N + 1)
    for u, v in edges:
        out[u] += 1
        in_[v] += 1
    D = [out[v] - in_[v] for v in range(N+1)]
    S = sum(1 for v in range(1, N+1) if D[v] != 0)
    
    if S == 0:
        if C == 1:
            print(0)
        else:
            print(C - 1)
    elif S == 2:
        a = 0
        b = 0
        for v in range(1, N+1):
            if D[v] != 0:
                if D[v] > 0:
                    a = D[v]
                else:
                    b = D[v]
        required_degree = a - 1
        required_connection = max(0, C - 1)
        minimal_edges = max(required_degree, required_connection)
        print(minimal_edges)
    else:
        required_degree = (S - 2 + 1) // 2
        required_connection = max(0, C - 1)
        minimal_edges = max(required_degree, required_connection)
        print(minimal_edges)

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