結果
問題 | No.1640 簡単な色塗り |
ユーザー |
![]() |
提出日時 | 2022-08-03 01:57:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 380 ms / 2,000 ms |
コード長 | 1,255 bytes |
コンパイル時間 | 515 ms |
コンパイル使用メモリ | 81,892 KB |
実行使用メモリ | 102,008 KB |
最終ジャッジ日時 | 2024-07-23 20:04:09 |
合計ジャッジ時間 | 23,915 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
N = int(input()) def f(n): return int(n) - 1 ab = [list(map(f,input().split())) for _ in range(N)] d = [0 for _ in range(N)] l = [0 for _ in range(N)] ll = [[] for _ in range(N)] lll = [0 for _ in range(N)] now = 0 for i in range(N): a,b = ab[i] d[a] += 1 d[b] += 1 ll[a].append(i) ll[b].append(i) from collections import deque que = deque() for i in range(N): if d[i] == 1: que.append(i) while now != N: while que: i = que.popleft() for j in ll[i]: if l[j] != 0: continue l[j] = i + 1 lll[i] = 1 d[i] -= 1 a,b = ab[j] c = a + b - i d[c] -= 1 if d[c] == 1: que.append(c) elif d[c] <= 0 and lll[c] == 0: print("No") exit() if l[now] != 0: now += 1 continue a,b = ab[now] if d[a] < d[b]: c = a else: c = b e = a + b - c l[now] = c + 1 lll[c] = 1 d[a] -= 1 d[b] -= 1 if d[e] == 1: que.append(e) now += 1 continue for i in range(N): if lll[i] == 0: print("No") exit() print("Yes") for i in range(len(l)): print(l[i])