結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2023-06-18 20:07:40 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 975 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 86,656 KB |
最終ジャッジ日時 | 2024-11-19 14:31:46 |
合計ジャッジ時間 | 3,991 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 RE * 2 |
other | AC * 1 RE * 20 |
ソースコード
class UnionFind:def __init__(self, n):self.par = [i for i in range(n + 1)]self.rank = [0] * (n + 1)# searchdef find(self, x):if self.par[x] == x:return xelse:self.par[x] = self.find(self.par[x])return self.par[x]# unitedef union(self, x, y):x = self.find(x)y = self.find(y)if self.rank[x] < self.rank[y]:self.par[x] = yelse:self.par[y] = xif self.rank[x] == self.rank[y]:self.rank[x] += 1# checkdef same_check(self, x, y):return self.find(x) == self.find(y)n, m = map(int, input().split())ab_list = [tuple(map(int, input().split())) for _ in range(m)]uf = UnionFind(n)for a, b in ab_list:uf.union(a, b)p_count = [0] * (n + 1)for i in range(n):p = uf.find(i + 1)p_count[p] += 1res = nfor i in range(n):res -= p_count[i + 1] // 2print(res)