結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー qwewe
提出日時 2025-04-24 12:25:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,773 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 92,020 KB
最終ジャッジ日時 2025-04-24 12:26:26
合計ジャッジ時間 4,951 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    out_degree = [0] * (N + 1)
    in_degree = [0] * (N + 1)
    adj = [[] for _ in range(N + 1)]  # Undirected adjacency list for BFS

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

    # Compute weak connected components using BFS
    visited = [False] * (N + 1)
    C = 0
    for v in range(1, N + 1):
        if not visited[v]:
            C += 1
            q = deque()
            q.append(v)
            visited[v] = True
            while q:
                u = q.popleft()
                for nei in adj[u]:
                    if not visited[nei]:
                        visited[nei] = True
                        q.append(nei)

    # Calculate d for each vertex
    d = [0] * (N + 1)
    for v in range(1, N + 1):
        d[v] = out_degree[v] - in_degree[v]

    # Compute sum_case1
    sum_case1 = sum(max(0, dv) for dv in d[1:])

    # Determine sum_case2
    has_positive = any(dv >= 1 for dv in d[1:])
    has_negative = any(dv <= -1 for dv in d[1:])

    if has_positive and has_negative:
        sum_case2 = sum_case1 - 1
    elif has_positive:
        sum_case2 = sum_case1
    else:
        sum_case2 = float('inf')

    K_degree = min(sum_case1, sum_case2)

    if K_degree == float('inf'):
        print(-1)
        return

    # Check connectivity condition
    if C == 1:
        print(K_degree)
    else:
        if K_degree >= C - 1:
            print(K_degree)
        else:
            print(-1)

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