結果
問題 | 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) - 1ab = [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 = 0for i in range(N):a,b = ab[i]d[a] += 1d[b] += 1ll[a].append(i)ll[b].append(i)from collections import dequeque = 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:continuel[j] = i + 1lll[i] = 1d[i] -= 1a,b = ab[j]c = a + b - id[c] -= 1if d[c] == 1:que.append(c)elif d[c] <= 0 and lll[c] == 0:print("No")exit()if l[now] != 0:now += 1continuea,b = ab[now]if d[a] < d[b]:c = aelse:c = be = a + b - cl[now] = c + 1lll[c] = 1d[a] -= 1d[b] -= 1if d[e] == 1:que.append(e)now += 1continuefor i in range(N):if lll[i] == 0:print("No")exit()print("Yes")for i in range(len(l)):print(l[i])