結果
問題 | No.1390 Get together |
ユーザー |
|
提出日時 | 2020-09-01 21:07:17 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,474 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 73,856 KB |
最終ジャッジ日時 | 2024-11-30 10:33:49 |
合計ジャッジ時間 | 3,959 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 29 |
ソースコード
class UnionFindVerSize(): def __init__(self, N): self._parent = [n for n in range(0, N)] self._size = [1] * N def find_root(self, x): if self._parent[x] == x: return x self._parent[x] = self.find_root(self._parent[x]) return self._parent[x] def unite(self, x, y): gx = self.find_root(x) gy = self.find_root(y) if gx == gy: return if self._size[gx] < self._size[gy]: self._parent[gx] = gy self._size[gy] += self._size[gx] else: self._parent[gy] = gx self._size[gx] += self._size[gy] def get_size(self, x): return self._size[self.find_root(x)] def is_same_group(self, x, y): return self.find_root(x) == self.find_root(y) def calc_group_num(self): N = len(self._parent) ans = 0 for i in range(N): if self.find_root(i) == i: ans += 1 return ans N,M = map(int,input().split()) b = list(map(int,input().split())) c = list(map(int,input().split())) box = [[] for i in range(M+1)] color = [0 for i in range(N)] for i in range(N): box[b[i]].append(c[i]-1) color[c[i]-1] += 1 uf = UnionFindVerSize(N) for i in range(M+1): for v in box[i]: uf.unite(v,box[i][0]) none_color = sum(int(color[i]==0) for i in range(N)) connected = uf.calc_group_num() - none_color B = sum(int(box[i]!=[]) for i in range(M+1)) print(B-connected)