結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
👑 ![]() |
提出日時 | 2023-08-23 06:37:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 821 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 81,612 KB |
最終ジャッジ日時 | 2024-11-14 12:25:24 |
合計ジャッジ時間 | 4,510 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
def uf_find(n,p):ufl = []while p[n] != n:ufl.append(n)n = p[n]for i in ufl:p[i] = nreturn ndef uf_union(a,b,p,rank):ap = uf_find(a,p)bp = uf_find(b,p)if ap == bp:return Trueelse:if rank[ap] > rank[bp]:p[bp] = apsize[ap] += size[bp]elif rank[ap] < rank[bp]:p[ap] = bpsize[bp] += size[ap]else:p[bp] = aprank[ap] += 1size[ap] += size[bp]return FalseN,M = map(int,input().split())N *= 2p = [i for i in range(N)]rank = [0] * Nsize = [1] * Nfor i in range(M):A,B = map(int,input().split())A-=1B-=1uf_union(A,B,p,rank)ans = 0for i in range(N):if uf_find(i,p)==i:ans += size[i]%2print (ans//2)