結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー lam6er
提出日時 2025-03-20 19:02:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,127 bytes
コンパイル時間 410 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 124,280 KB
最終ジャッジ日時 2025-03-20 19:03:03
合計ジャッジ時間 5,147 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict, deque

def input():
    return stdin.read()

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    u = []
    v = []
    adj = [[] for _ in range(N+1)]  # undirected adjacency list

    in_deg = [0] * (N+1)
    out_deg = [0] * (N+1)

    for _ in range(M):
        U = int(data[idx]); idx +=1
        V = int(data[idx]); idx +=1
        u.append(U)
        v.append(V)
        out_deg[U] += 1
        in_deg[V] += 1
        adj[U].append(V)
        adj[V].append(U)
    
    # Compute connected components (undirected)
    visited = [False]*(N+1)
    components = 0
    for i in range(1, N+1):
        if not visited[i]:
            components += 1
            q = deque()
            q.append(i)
            visited[i] = True
            while q:
                node = q.popleft()
                for neighbor in adj[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        q.append(neighbor)
    
    # Compute diffs
    diffs = [0]*(N+1)
    for i in range(1, N+1):
        diffs[i] = in_deg[i] - out_deg[i]
    
    pos_sum = 0
    neg_sum = 0
    for d in diffs[1:]:
        if d >0:
            pos_sum += d
        else:
            neg_sum += d
    
    # Check if it's possible to satisfy:
    # Either all diffs are zero (pos_sum=0)
    # Or exactly two nodes have diff +1 and -1, others zero
    possible = False

    # Case when the graph is already connected (components == 1)
    if components == 1:
        temp_pos = sum(1 for d in diffs[1:] if d != 0)
        if pos_sum ==0 and temp_pos ==0:
            # Eulerian circuit
            print(0)
            return
        else:
            # Check if we have exactly two nodes: one +1 and one -1
            candidates = []
            for d in diffs[1:]:
                if d ==0:
                    continue
                candidates.append(d)
            if len(candidates) ==2 and ((candidates[0] ==1 and candidates[1] ==-1) or (candidates[0]==-1 and candidates[1]==1)):
                print(0)
                return
        
        # Not already Eulerian. Need to add edges.
        # Find the minimal possible between (pos_sum) and (pos_sum -1)
        minimal = min(pos_sum, pos_sum-1) if pos_sum >=1 else pos_sum
        if components ==1 and ((pos_sum - minimal) ==0 or (pos_sum - minimal) ==1):
            print(minimal)
            return
        else:
            # Check if possible to achieve
            possible = (pos_sum >=0)
    else:
        # Must add (components-1) edges to connect
        # Now, S may be adjusted, but how?
        # Assume that each edge added can reduce the pos_sum by 1
        # So the total pos_sum after adding (c-1) edges is pos_sum - (c-1)
        S_after = pos_sum - (components -1)
        # Also, need to ensure S_after and the adjustment to form the required conditions
        if S_after >=0:
            # possible to form either case a or b
            candidates = []
            if S_after ==0:
                # case a
                minimal = (components -1) + 0
            else:
                # case b or a
                minimal_case_b = (components -1) + (S_after -1)
                minimal_case_a = (components -1) + S_after
                minimal = min(minimal_case_a, minimal_case_b)
            
            # Additionally, check if after adding these edges, the underlying graph is connected
            # which it is, since components -1 edges are added.
            print(minimal)
        else:
            # Cannot have S_after >=0, so impossible
            print(-1)
        return
    
    # For components == 1:
    S = pos_sum
    minimal = min(S, S-1) if S >=1 else S
    # Check if the adjustment is possible (no violation)
    # Sum is possible when minimal = S-1, which requires that the result is exactly 1 and -1
    # For this, the current S must be at least 1
    print(minimal if (components ==1 and S >=0) else -1)

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