結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
|
提出日時 | 2024-04-03 21:21:32 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,073 ms / 2,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 444 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 62,776 KB |
最終ジャッジ日時 | 2024-10-01 00:06:19 |
合計ジャッジ時間 | 15,162 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
class UnionFind: def __init__(self, n): self.n = n self.parent_size = [-1] * n def leader(self, a): if self.parent_size[a] < 0: return a self.parent_size[a] = self.leader(self.parent_size[a]) return self.parent_size[a] def merge(self, a, b): x, y = self.leader(a), self.leader(b) if x == y: return if abs(self.parent_size[x]) < abs(self.parent_size[y]): x, y = y, x self.parent_size[x] += self.parent_size[y] self.parent_size[y] = x return def same(self, a, b): return self.leader(a) == self.leader(b) def size(self, a): return abs(self.parent_size[self.leader(a)]) def groups(self): result=[[] for _ in range(self.n)] for i in range(self.n): result[self.leader(i)].append(i) return [r for r in result if r != []] N,M=map(int,input().split()) C=list(map(int,input().split())) uf=UnionFind(N) for _ in range(M): u,v=map(int,input().split()) u-=1;v-=1 if C[u]==C[v]:uf.merge(u,v) from collections import defaultdict D=defaultdict(set) for i in range(N): L=uf.leader(i) D[C[L]].add(L) ans=0 for k,v in D.items(): ans+=len(v)-1 print(ans)