結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー qwewe
提出日時 2025-05-14 12:49:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,889 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 88,284 KB
最終ジャッジ日時 2025-05-14 12:50:25
合計ジャッジ時間 3,910 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, stdin.readline().split())
    in_degree = [0] * (N + 1)
    out_degree = [0] * (N + 1)
    adj_undirected = [[] for _ in range(N + 1)]  # For connected components

    for _ in range(M):
        u, v = map(int, stdin.readline().split())
        out_degree[u] += 1
        in_degree[v] += 1
        adj_undirected[u].append(v)
        adj_undirected[v].append(u)  # undirected

    # Compute d_initial for each node
    d_initial = [0] * (N + 1)
    sum_d_initial = 0
    for u in range(1, N + 1):
        d = out_degree[u] - in_degree[u]
        d_initial[u] = d
        sum_d_initial += abs(d)

    # Check for open scenario
    max_d = max(d_initial)
    min_d = min(d_initial)
    has_positive = max_d >= 1
    has_negative = min_d <= -1

    K_closed = float('inf')
    if sum_d_initial % 2 == 0:
        K_closed = sum_d_initial // 2

    K_open = float('inf')
    if has_positive and has_negative:
        new_sum = sum_d_initial - 2
        if new_sum >= 0 and new_sum % 2 == 0:
            K_open = new_sum // 2

    K_degree = min(K_closed, K_open)

    # Compute connected components
    visited = [False] * (N + 1)
    C = 0
    for u in range(1, N + 1):
        if not visited[u]:
            C += 1
            stack = [u]
            visited[u] = True
            while stack:
                node = stack.pop()
                for neighbor in adj_undirected[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        stack.append(neighbor)

    K_connect = max(0, C - 1)

    answer = max(K_degree, K_connect) if K_degree != float('inf') else float('inf')

    if answer == float('inf'):
        print(-1)
    else:
        print(answer)

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