結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
![]() |
提出日時 | 2024-01-04 10:37:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 463 ms / 2,000 ms |
コード長 | 1,493 bytes |
コンパイル時間 | 470 ms |
コンパイル使用メモリ | 82,580 KB |
実行使用メモリ | 110,824 KB |
最終ジャッジ日時 | 2024-09-27 18:36:54 |
合計ジャッジ時間 | 8,421 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
class UnionFind: def __init__(self, n): self.par = [-1]*n # 要素の根(親) self.rank = [0]*n # 要素が属している木の高さ self.siz = [1]*n # 要素が属している木の大きさ(要素数) # xのroot(Find) def root(self, x): if self.par[x] == -1: return x else: self.par[x] = self.root(self.par[x]) return self.par[x] # xとyをmerge(Union) def merge(self, x, y): rx,ry = self.root(x), self.root(y) if rx == ry: return False if self.rank[rx] < self.rank[ry]: rx,ry = ry,rx # rx: 親, ry: 子 self.par[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 self.siz[rx] += self.siz[ry] return True # xとyが同一のgroupかどうか def issame(self, x, y): return self.root(x) == self.root(y) # xが含まれる木のサイズ def size(self, x): return self.siz[self.root(x)] #--------------------------------------------------- N,M = map(int,input().split()) uf = UnionFind(N) C = list(map(int,input().split())) for _ in range(M): u,v = map(int,input().split()) if C[u-1] != C[v-1]: continue uf.merge(u-1, v-1) par = [set() for _ in range(N)] for i in range(N): idx = uf.root(i) par[C[i] - 1].add(idx) ans = 0 for p in par: if not p: continue ans += len(p) - 1 print(ans)