結果
問題 |
No.1390 Get together
|
ユーザー |
|
提出日時 | 2021-02-13 09:48:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 466 ms / 2,000 ms |
コード長 | 1,564 bytes |
コンパイル時間 | 244 ms |
コンパイル使用メモリ | 82,080 KB |
実行使用メモリ | 148,080 KB |
最終ジャッジ日時 | 2024-07-20 12:17:45 |
合計ジャッジ時間 | 9,276 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
n,m=map(int,input().split()) bc=[list(map(int,input().split())) for _ in range(n)] # UnionFind class UnionFind: def __init__(self,n): self.n=n self.par=[-1]*n # par[i]:i根ならグループiの要素数に-1をかけたもの。i根じゃないならiの親 self.rank=[0]*n # iの根を返す def find(self,i): if self.par[i]<0:return i ii=i while self.par[i]>=0: i=self.par[i] while i!=self.par[ii]: ii,self.par[ii]=self.par[ii],i return i # iとjをunionし、根頂点を返す def union(self,i,j): i,j=self.find(i),self.find(j) if i==j:return i elif self.rank[i]>self.rank[j]: # par[i]:グループiの要素数で判断してもいい self.par[i]+=self.par[j] self.par[j]=i else: self.par[j]+=self.par[i] self.par[i]=j # 深さ(rank)が同じものを併合した場合1を足す if self.rank[i]==self.rank[j]: self.rank[j]+=1 return self.find(i) # iとjが同じグループに属するか判断 def same(self,i,j): return self.find(i)==self.find(j) # ノードiが属する木のサイズを返す def size(self,i): return -self.par[self.find(i)] uf=UnionFind(m) cd={} for b,c in bc: b,c=b-1,c-1 # b:箱,c:色 if c in cd: cd[c].add(b) else: cd[c]={b} ans=0 for c in cd: if len(cd[c])==1:continue u=cd[c].pop() v=cd[c].pop() if uf.same(u,v): pass else: uf.union(u,v) ans+=1 for s in cd[c]: if uf.same(u,s): pass else: uf.union(u,s) ans+=1 print(ans)