結果

問題 No.1640 簡単な色塗り
ユーザー lam6er
提出日時 2025-04-15 21:38:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 230 ms / 2,000 ms
コード長 2,307 bytes
コンパイル時間 456 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 97,208 KB
最終ジャッジ日時 2025-04-15 21:40:28
合計ジャッジ時間 14,817 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N = int(sys.stdin.readline())
    AB = []
    edges = [[] for _ in range(N + 1)]  # edges[v] contains list of indices i where v is in AB[i]
    count = [0] * (N + 1)  # 1-based
    for i in range(N):
        a, b = map(int, sys.stdin.readline().split())
        AB.append((a, b))
        edges[a].append(i)
        edges[b].append(i)
        count[a] += 1
        count[b] += 1

    # Check if all nodes appear at least once
    for v in range(1, N + 1):
        if count[v] == 0:
            print("No")
            return

    # Initialize queue with nodes having count 1
    queue = deque()
    count_current = [0] * (N + 1)
    for v in range(1, N + 1):
        count_current[v] = count[v]
    for v in range(1, N + 1):
        if count_current[v] == 1:
            queue.append(v)

    processed = [False] * N
    choice = [0] * N
    covered = [False] * (N + 1)

    # Process nodes with count 1
    while queue:
        v = queue.popleft()
        found = False
        for i in edges[v]:
            if not processed[i]:
                processed[i] = True
                a, b = AB[i]
                if a == v:
                    choice[i] = a
                else:
                    choice[i] = b
                covered[v] = True
                u = a if b == v else b
                count_current[u] -= 1
                if count_current[u] == 1:
                    queue.append(u)
                found = True
                break
        if not found:
            print("No")
            return

    # Process remaining operations
    for i in range(N):
        if not processed[i]:
            a, b = AB[i]
            if not covered[a] and not covered[b]:
                choice[i] = a
                covered[a] = True
            elif not covered[a]:
                choice[i] = a
                covered[a] = True
            elif not covered[b]:
                choice[i] = b
                covered[b] = True
            else:
                choice[i] = a
            processed[i] = True

    # Check if all nodes are covered
    for v in range(1, N + 1):
        if not covered[v]:
            print("No")
            return

    print("Yes")
    for c in choice:
        print(c)

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