結果
問題 |
No.2563 色ごとのグループ
|
ユーザー |
|
提出日時 | 2024-06-07 13:58:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 454 ms / 2,000 ms |
コード長 | 1,900 bytes |
コンパイル時間 | 262 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 138,880 KB |
最終ジャッジ日時 | 2024-12-25 18:41:22 |
合計ジャッジ時間 | 8,809 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
class UnionFind: def __init__(self, n): self._n = n self._parent = [-1] * n self._roots = set(range(n)) def _find(self, x): if self._parent[x] < 0: return x self._parent[x] = self._find(self._parent[x]) return self._parent[x] def union(self, x, y): x, y = self._find(x), self._find(y) if x == y: return if self._parent[y] < self._parent[x]: x, y = y, x self._parent[x] += self._parent[y] self._parent[y] = x self._roots.discard(y) def same(self, x, y): return self._find(x) == self._find(y) def size(self, x): return -self._parent[self._find(x)] def members(self, x): root = self._find(x) return [i for i in range(self._n) if self._find(i) == root] def all_group_members(self): group_members = dict() for member in range(self._n): root = self._find(member) if root not in group_members: group_members[root] = [] group_members[root].append(member) return group_members def root(self, x): return self._find(x) def roots(self): return self._roots def group_count(self): return len(self.roots()) def group_numbers(self): return [self._find(i) for i in range(self._n)] def __str__(self): return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items()) 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, v = u - 1, v - 1 if C[u] == C[v]: uf.union(u, v) from collections import defaultdict d = defaultdict(set) for i, c in enumerate(C): d[c].add(uf.root(i)) ans = 0 for v in d.values(): ans += len(v) - 1 print(ans)