結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2023-08-12 15:47:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 279 ms / 2,000 ms |
コード長 | 1,496 bytes |
コンパイル時間 | 271 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 104,584 KB |
最終ジャッジ日時 | 2024-11-14 12:24:24 |
合計ジャッジ時間 | 5,264 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
from collections import defaultdictclass UnionFind:def __init__(self, n):self.data = [-1] * (n + 1)self.nexts = [-1] * (n + 1) # 次の要素(なければ-1)self.tails = list(range(n + 1)) # 末尾の要素def root(self, a: int) -> int:if self.data[a] < 0: return aself.data[a] = self.root(self.data[a])return self.data[a]def unite(self, a: int, b: int) -> bool:pa = self.root(a)pb = self.root(b)if pa == pb: return Falseif self.data[pa] > self.data[pb]:pa, pb = pb, paself.data[pa] += self.data[pb] # pa を pb をつなげるself.data[pb] = pa# pa の末尾に pb を繋げるself.nexts[self.tails[pa]] = pbself.tails[pa] = self.tails[pb]return Truedef issame(self, a: int, b: int) -> bool:return self.root(a) == self.root(b)def size(self, a: int) -> int:"""a が属する集合のサイズ"""return -self.data[self.root(a)]def group(self, a):"""a が属する集合"""v = self.root(a)while v != -1:yield vv = self.nexts[v]N, M = map(int, input().split())uf = UnionFind(2 * N)for _ in range(M):A, B = map(lambda x: int(x)-1, input().split())uf.unite(A, B)used = set()ans = Nfor i in range(2 * N):p = uf.root(i)if p in used: continueused.add(p)ans -= uf.size(i) // 2print(ans)