結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー lam6er
提出日時 2025-04-09 20:58:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,231 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 82,856 KB
実行使用メモリ 79,528 KB
最終ジャッジ日時 2025-04-09 21:00:24
合計ジャッジ時間 4,451 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [1] * (n + 1)
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

def main():
    n, m = map(int, stdin.readline().split())
    if m == 0:
        print(0)
        return
    
    edges = []
    in_degree = [0] * (n + 1)
    out_degree = [0] * (n + 1)
    dsu = DSU(n)
    nodes_with_edges = set()
    
    for _ in range(m):
        u, v = map(int, stdin.readline().split())
        in_degree[v] += 1
        out_degree[u] += 1
        dsu.union(u, v)
        nodes_with_edges.add(u)
        nodes_with_edges.add(v)
    
    # Check connectivity of underlying undirected graph for nodes involved in edges
    if nodes_with_edges:
        root = dsu.find(next(iter(nodes_with_edges)))
        for node in nodes_with_edges:
            if dsu.find(node) != root:
                print(-1)
                return
    
    delta = [out_degree[i] - in_degree[i] for i in range(n + 1)]
    
    # Case 1: Eulerian circuit, all delta must be zero
    sum_positive_case1 = 0
    for i in delta:
        if i > 0:
            sum_positive_case1 += i
    
    # Case 2: Eulerian trail, two nodes have +1 and -1
    sum_abs = sum(abs(d) for d in delta)
    has_positive = any(d >= 1 for d in delta)
    has_negative = any(d <= -1 for d in delta)
    
    min_case2 = float('inf')
    if has_positive and has_negative:
        if (sum_abs - 2) % 2 == 0:
            candidate = (sum_abs - 2) // 2
            if candidate >= 0:
                min_case2 = candidate
    
    min_k = min(sum_positive_case1, min_case2)
    if min_k != float('inf'):
        print(min_k)
    else:
        print(-1)

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