結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-08-12 13:49:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 353 ms / 2,000 ms |
コード長 | 1,517 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 113,632 KB |
最終ジャッジ日時 | 2024-11-14 12:21:59 |
合計ジャッジ時間 | 5,771 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
class UnionFind:def __init__(self, n, w=None):self.par = [-1]*nself.rank = [0]*nself.siz = [1]*nself.cnt = nself.min_node = [i for i in range(n)]self.weight = w if w else [1]*ndef root(self, x):if self.par[x] == -1:return xself.par[x] = self.root(self.par[x])return self.par[x]def issame(self, x, y):return self.root(x) == self.root(y)def unite(self, x, y):px = self.root(x)py = self.root(y)if px == py:return Falseif self.rank[px] < self.rank[py]:px, py = py, pxself.par[py] = pxif self.rank[px] == self.rank[py]:self.rank[px] += 1self.siz[px] += self.siz[py]self.cnt -= 1self.min_node[px] = min(self.min_node[px], self.min_node[py])self.weight[px] += self.weight[py]return Falsedef count(self):return self.cntdef min(self, x):return self.min_node[self.root(x)]def getweight(self, x):return self.weight[self.root(x)]def size(self, x):return self.siz[self.root(x)]N, M = map(int, input().split())AB = [list(map(int, input().split())) for _ in range(M)]UF = UnionFind(2*N)for a, b in AB:a-=1b-=1UF.unite(a, b)cnt = dict()for i in range(2*N):r = UF.root(i)s = UF.size(r)cnt[r] = s%2ans = 0for key in cnt:ans += cnt[key]print(ans//2)