結果
問題 | No.1640 簡単な色塗り |
ユーザー |
![]() |
提出日時 | 2021-08-06 22:09:46 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 728 ms / 2,000 ms |
コード長 | 1,682 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 53,248 KB |
最終ジャッジ日時 | 2024-06-29 15:17:40 |
合計ジャッジ時間 | 27,888 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 TLE * 1 |
ソースコード
import sys input = sys.stdin.readline N=int(input()) # UnionFind Group = [i for i in range(N+1)] # グループ分け Nodes = [1]*(N+1) # 各グループのノードの数 def find(x): while Group[x] != x: x=Group[x] return x def Union(x,y): if find(x) != find(y): if Nodes[find(x)] < Nodes[find(y)]: Nodes[find(y)] += Nodes[find(x)] Nodes[find(x)] = 0 Group[find(x)] = find(y) else: Nodes[find(x)] += Nodes[find(y)] Nodes[find(y)] = 0 Group[find(y)] = find(x) DEG=[0]*(N+1) E=[[] for i in range(N+1)] for i in range(N): a,b=map(int,input().split()) DEG[a]+=1 DEG[b]+=1 E[a].append((b,i)) E[b].append((a,i)) Q=[] for i in range(N+1): if DEG[i]==1: Q.append(i) ANS=[-1]*N USE=[0]*(N+1) USE[0]=1 while Q: x=Q.pop() USE[x]=1 for to,ind in E[x]: if USE[to]==0: ANS[ind]=x DEG[to]-=1 if DEG[to]==1: Q.append(to) for i in range(N+1): if USE[i]==0: NOW=i while True: flag=0 USE[NOW]=1 for to,ind in E[NOW]: if USE[to]==0: ANS[ind]=NOW NOW=to flag=1 break if flag==0: for to,ind in E[NOW]: if ANS[ind]==-1: ANS[ind]=NOW break break if -1 in ANS: print("No") else: print("Yes") for ans in ANS: print(ans)