結果

問題 No.1610 She Loves Me, She Loves Me Not, ...
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:46:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 2,159 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 79,676 KB
最終ジャッジ日時 2025-03-26 15:46:59
合計ジャッジ時間 3,653 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = int(input[idx])
        idx += 1
        b = int(input[idx])
        idx += 1
        adj[a].append(b)
        adj[b].append(a)

    # Find connected components
    visited = [False] * (N + 1)
    components = []
    for u in range(1, N + 1):
        if not visited[u]:
            q = deque()
            q.append(u)
            visited[u] = True
            comp = set()
            comp.add(u)
            while q:
                v = q.popleft()
                for nei in adj[v]:
                    if not visited[nei]:
                        visited[nei] = True
                        comp.add(nei)
                        q.append(nei)
            components.append(comp)

    total_steps = 0

    for comp in components:
        # Compute edges_in_C
        edges_in_C = 0
        for u in comp:
            for v in adj[u]:
                if v in comp and u < v:
                    edges_in_C += 1

        # Compute degrees
        degree = {u: 0 for u in comp}
        for u in comp:
            cnt = 0
            for v in adj[u]:
                if v in comp:
                    cnt += 1
            degree[u] = cnt

        # Process queue
        q = deque()
        for u in comp:
            if degree[u] == 1:
                q.append(u)

        while q:
            u = q.popleft()
            if degree[u] != 1:
                continue
            for v in adj[u]:
                if v not in comp:
                    continue
                if degree[v] == 0:
                    continue
                degree[v] -= 1
                if degree[v] == 1:
                    q.append(v)
            degree[u] = 0

        sum_deg = sum(degree.values())
        edges_2core = sum_deg // 2
        steps = edges_in_C - edges_2core
        total_steps += steps

    if total_steps % 2 == 1:
        print("Yes")
    else:
        print("No")

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