結果
問題 | No.1640 簡単な色塗り |
ユーザー |
|
提出日時 | 2023-03-10 02:45:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 283 ms / 2,000 ms |
コード長 | 1,272 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 99,328 KB |
最終ジャッジ日時 | 2024-09-18 03:13:03 |
合計ジャッジ時間 | 17,145 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
from collections import dequen = int(input())g = [[] for _ in range(n)]deg = [0 for _ in range(n)]used = [False for _ in range(n)]ans = [None for _ in range(n)]for e in range(n):a, b = map(int, input().split())a -= 1b -= 1if a == b:used[a] = Trueans[e] = a + 1else:g[a].append((b, e))g[b].append((a, e))deg[a] += 1deg[b] += 1dq = deque()for u in range(n):if used[u]:continueif deg[u] == 0:print("No")exit()elif deg[u] == 1:used[u] = Truedq.append(u)while len(dq) > 0:cur = dq.popleft()for nxt, e in g[cur]:if not ans[e] is None:continuedeg[nxt] -= 1ans[e] = cur + 1if used[nxt]:continueif deg[nxt] == 0:print("No")exit()elif deg[nxt] == 1:used[nxt] = Truedq.append(nxt)for src in range(n):if used[src]:continuedq.append(src)used[src] = Truewhile len(dq) > 0:cur = dq.popleft()while len(g[cur]) > 0:nxt, e = g[cur].pop()if not ans[e] is None:continueans[e] = cur + 1if used[nxt]:continueused[nxt] = Truedq.append(nxt)breakif ans.count(None) > 0:print("No")else:print("Yes")print(*ans, sep="\n")