結果
問題 | No.2563 色ごとのグループ |
ユーザー |
![]() |
提出日時 | 2023-12-02 15:07:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 637 ms / 2,000 ms |
コード長 | 1,393 bytes |
コンパイル時間 | 452 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 214,040 KB |
最終ジャッジ日時 | 2024-09-26 18:08:06 |
合計ジャッジ時間 | 10,417 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import sysinput = sys.stdin.readlineN,M = map(int,input().split())C = list(map(int,input().split()))UV = [tuple(map(int,input().split())) for _ in range(M)]vs = [[] for _ in range(N+1)]for i,c in enumerate(C):vs[c].append(i)es = [[] for _ in range(N+1)]for u,v in UV:u,v = u-1,v-1if C[u] != C[v]: continuees[C[u]].append((u,v))class UnionFind:def __init__(self,N):self.parent = [i for i in range(N)]self._size = [1] * Nself.count = 0def root(self,a):if self.parent[a] == a:return aelse:self.parent[a] = self.root(self.parent[a])return self.parent[a]def is_same(self,a,b):return self.root(a) == self.root(b)def unite(self,a,b):ra = self.root(a)rb = self.root(b)if ra == rb: returnif self._size[ra] < self._size[rb]: ra,rb = rb,raself._size[ra] += self._size[rb]self.parent[rb] = raself.count += 1def size(self,a):return self._size[self.root(a)]ans = 0for c in range(N+1):if not vs[c]: continuess = sorted(set(vs[c]))ds = {a:i for i,a in enumerate(ss)}uf = UnionFind(len(ss))for u,v in es[c]:i,j = ds[u],ds[v]uf.unite(i,j)rs = set()for i in range(len(ss)):rs.add(uf.root(i))ans += len(rs) - 1print(ans)