結果

問題 No.2418 情報通だよ!Nafmoくん
ユーザー Basin-Bug
提出日時 2023-08-12 14:36:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 683 ms / 2,000 ms
コード長 2,588 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 144,372 KB
最終ジャッジ日時 2024-11-14 12:23:53
合計ジャッジ時間 8,927 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import collections
class UnionFind():
def __init__(self):
'''
unionfind,tuple,
'''
self.parents = dict() # {:ID,}
self.members_set = collections.defaultdict(lambda : set()) # keyvalue(tuple)
self.roots_set = set() # (tuple)
self.key_ID = dict() # ID
self.ID_key = dict() # ID
self.cnt = 0 # ID
def dictf(self,x): # ID
if x in self.key_ID:
return self.key_ID[x]
else:
self.cnt += 1
self.key_ID[x] = self.cnt
self.parents[x] = self.cnt
self.ID_key[self.cnt] = x
self.members_set[x].add(x)
self.roots_set.add(x)
return self.key_ID[x]
def find(self, x):
ID_x = self.dictf(x)
if self.parents[x] == ID_x:
return x
else:
self.parents[x] = self.key_ID[self.find(self.ID_key[self.parents[x]])]
return self.ID_key[self.parents[x]]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if self.parents[x] > self.parents[y]:
x, y = y, x
if x == y:
return
for i in self.members_set[y]:
self.members_set[x].add(i)
self.members_set[y] = set()
self.roots_set.remove(y)
self.parents[y] = self.key_ID[x]
def size(self, x):#x
return len(self.members_set[self.find(x)])
def same(self, x, y):#
return self.find(x) == self.find(y)
def members(self, x):#x
return self.members_set[self.find(x)]
def roots(self):#
return self.roots_set
def group_count(self):#
return len(self.roots_set)
def all_group_members(self):#
return {r: self.members_set[r] for r in self.roots_set}
uf = UnionFind()
N, M = map(int, input().split())
for i in range(M):
a, b = map(int, input().split())
uf.union(a, b)
ans = N
for i in uf.roots():
ans -= uf.size(i) // 2
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0