結果

問題 No.2563 色ごとのグループ
ユーザー Basin-Bug
提出日時 2023-12-02 15:52:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,596 ms / 2,000 ms
コード長 2,867 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 81,952 KB
実行使用メモリ 262,016 KB
最終ジャッジ日時 2024-09-26 19:25:57
合計ジャッジ時間 15,776 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

import collections
from collections import defaultdict
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}
N, M = map(int, input().split())
C = list(map(int, input().split()))
colors = collections.defaultdict(list)
for i in range(N):
colors[C[i]].append(i + 1)
uf = UnionFind()
for i in range(M):
u, v = map(int, input().split())
if C[u - 1] == C[v - 1]:
uf.union(u, v)
ans = 0
for i in colors.keys():
m = colors[i][0]
for n in colors[i]:
if not uf.same(n, m):
uf.union(n, m)
ans += 1
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0