結果

問題 No.1640 簡単な色塗り
ユーザー lam6er
提出日時 2025-04-15 21:43:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 204 ms / 2,000 ms
コード長 2,412 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 96,764 KB
最終ジャッジ日時 2025-04-15 21:44:54
合計ジャッジ時間 13,448 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N = int(sys.stdin.readline())
    edges = []
    for _ in range(N):
        a, b = map(int, sys.stdin.readline().split())
        edges.append((a-1, b-1))  # Convert to 0-based indices
    
    # Check if all vertices appear at least once
    present = [False] * N
    for a, b in edges:
        present[a] = True
        present[b] = True
    if not all(present):
        print("No")
        return
    
    # Build edge lists for each vertex
    edge_lists = [[] for _ in range(N)]
    for i, (a, b) in enumerate(edges):
        edge_lists[a].append(i)
        edge_lists[b].append(i)
    
    # Calculate degrees
    degree = [len(lst) for lst in edge_lists]
    
    # Initialize queue with degree 1 vertices
    q = deque()
    for v in range(N):
        if degree[v] == 1:
            q.append(v)
    
    processed_edges = [False] * N
    choices = [0] * N
    used = [False] * N
    
    # Process degree 1 vertices
    while q:
        v = q.popleft()
        # Find the unprocessed edge for v
        edge_found = -1
        for e in edge_lists[v]:
            if not processed_edges[e]:
                edge_found = e
                break
        if edge_found == -1:
            print("No")
            return
        a, b = edges[edge_found]
        # Determine which one is v
        selected = v
        processed_edges[edge_found] = True
        choices[edge_found] = selected + 1  # Convert back to 1-based
        used[selected] = True
        # Get the other vertex
        other = a if selected != a else b
        # Decrease degree of other
        degree[other] -= 1
        if degree[other] == 0:
            print("No")
            return
        if degree[other] == 1:
            q.append(other)
    
    # Process remaining edges
    for i in range(N):
        if not processed_edges[i]:
            a, b = edges[i]
            # Choose the one not used yet
            if not used[a]:
                selected = a
            elif not used[b]:
                selected = b
            else:
                # Both are used, choose arbitrarily (A)
                selected = a
            choices[i] = selected + 1
            used[selected] = True
    
    # Final check
    if all(used):
        print("Yes")
        for c in choices:
            print(c)
    else:
        print("No")

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