結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-08-12 14:17:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 296 ms / 2,000 ms |
コード長 | 659 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,096 KB |
実行使用メモリ | 104,764 KB |
最終ジャッジ日時 | 2024-11-14 12:23:30 |
合計ジャッジ時間 | 5,287 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
from collections import Counter class UnionFind(): def __init__(self,n): self.parents = list(range(n)) def find(self, x): if self.parents[x] == x: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): px = self.find(x) py = self.find(y) if px != py: self.parents[px] = py def main(): n,m=map(int,input().split()) uf = UnionFind(2*n+1) for i in range(m): a,b=map(int,input().split()) uf.union(a,b) p = [uf.find(x) for x in range(2*n+1)] c = Counter(p[1:]) ans = 0 for v in c.values(): if v % 2 == 1: ans += 1 print(ans//2) if __name__ == "__main__": main()