結果
問題 | No.2563 色ごとのグループ |
ユーザー |
![]() |
提出日時 | 2023-12-02 15:49:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 439 ms / 2,000 ms |
コード長 | 1,581 bytes |
コンパイル時間 | 393 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 130,988 KB |
最終ジャッジ日時 | 2024-09-26 19:22:08 |
合計ジャッジ時間 | 7,572 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
# 違う色の頂点をつなぐ辺は無視してよい。 # 閉路を作っても意味ないので無視してよい。 # 辺が同じ色同士かつ閉路を持っていない場合 UnionFindでくっつける。 # 各集合の大きさを把握しておく。 # Σ色, (UnionFindでのその色の集合の個数 - 1) 本だけ線を入れる必要がある。 class UnionFind: def __init__(self, size): self.parent = list(range(size)) self.rank = [0] * size def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # Path compression return self.parent[x] def union(self, x, y): px = self.find(x) py = self.find(y) if px == py: # Already in the same set return # Union by rank if self.rank[px] > self.rank[py]: self.parent[py] = px elif self.rank[px] < self.rank[py]: self.parent[px] = py else: self.parent[py] = px self.rank[px] += 1 N, M = map(int, input().split()) C = list(map(int, input().split())) uf = UnionFind(N) for i in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 if (C[u] == C[v]): uf.union(u, v) parents = set() for i in range(N): parents.add(uf.find(i)) parentcolor = dict() for parent in parents: if (not C[parent] in parentcolor): parentcolor[C[parent]] = 1 else: parentcolor[C[parent]] += 1 ans = 0 for key, value in parentcolor.items(): ans += value - 1 print(ans)