結果
問題 | No.2563 色ごとのグループ |
ユーザー | Nikkuniku029 |
提出日時 | 2023-12-02 16:02:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 395 ms / 2,000 ms |
コード長 | 2,876 bytes |
コンパイル時間 | 554 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 109,176 KB |
最終ジャッジ日時 | 2023-12-02 16:02:58 |
合計ジャッジ時間 | 7,184 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
55,612 KB |
testcase_01 | AC | 36 ms
55,612 KB |
testcase_02 | AC | 34 ms
55,612 KB |
testcase_03 | AC | 36 ms
55,612 KB |
testcase_04 | AC | 36 ms
55,612 KB |
testcase_05 | AC | 39 ms
55,612 KB |
testcase_06 | AC | 36 ms
55,612 KB |
testcase_07 | AC | 34 ms
55,612 KB |
testcase_08 | AC | 34 ms
55,612 KB |
testcase_09 | AC | 36 ms
55,612 KB |
testcase_10 | AC | 37 ms
55,612 KB |
testcase_11 | AC | 39 ms
55,612 KB |
testcase_12 | AC | 36 ms
55,612 KB |
testcase_13 | AC | 37 ms
55,612 KB |
testcase_14 | AC | 62 ms
73,132 KB |
testcase_15 | AC | 63 ms
73,104 KB |
testcase_16 | AC | 62 ms
73,112 KB |
testcase_17 | AC | 62 ms
73,116 KB |
testcase_18 | AC | 47 ms
64,564 KB |
testcase_19 | AC | 77 ms
76,556 KB |
testcase_20 | AC | 73 ms
77,416 KB |
testcase_21 | AC | 74 ms
76,792 KB |
testcase_22 | AC | 75 ms
76,684 KB |
testcase_23 | AC | 76 ms
76,684 KB |
testcase_24 | AC | 158 ms
87,836 KB |
testcase_25 | AC | 141 ms
89,684 KB |
testcase_26 | AC | 173 ms
97,812 KB |
testcase_27 | AC | 165 ms
108,412 KB |
testcase_28 | AC | 225 ms
100,936 KB |
testcase_29 | AC | 226 ms
108,872 KB |
testcase_30 | AC | 231 ms
108,872 KB |
testcase_31 | AC | 234 ms
108,872 KB |
testcase_32 | AC | 228 ms
108,872 KB |
testcase_33 | AC | 395 ms
109,176 KB |
testcase_34 | AC | 365 ms
108,608 KB |
testcase_35 | AC | 372 ms
108,608 KB |
testcase_36 | AC | 388 ms
109,176 KB |
testcase_37 | AC | 373 ms
109,176 KB |
ソースコード
class UnionFind: def __init__(self, n: int) -> None: """ 初期化 Parameters ---------- n:要素数 """ self.par = [-1] * (n + 1) self.rank = [0] * (n + 1) def root(self, x: int) -> int: """ xの属するグループの親番号を返す Parameters ---------- x:要素番号 Return ------ res:int xの属するグループの親番号 """ if self.par[x] == -1: return x else: self.par[x] = self.root(self.par[x]) return self.par[x] def issame(self, x, y) -> bool: """ xとyが同じグループに属するかどうかを返す Parameters ---------- x,y:要素番号 Return ------ res:bool true:xとyは同じグループである false:xとyは同じグループでない """ return self.root(x) == self.root(y) def unite(self, x, y) -> bool: """ xの属するグループとyの属するグループを併合する Parameters ---------- x,y:要素番号 Return ------ res:bool true:xとy、それぞれの属するグループを併合する false:xとyはすでに同じグループのため、併合は行わない """ x = self.root(x) y = self.root(y) # 既に同じグループなら何もしない if x == y: return False # unionbysize if self.rank[x] < self.rank[y]: self.par[x] = y else: self.par[y] = x if self.rank[x] == self.rank[y]: self.rank[x] += 1 return True def rank(self, x) -> int: """ xの高さを返す Return ------ res:int xの属する根付き木の高さ """ return self.rank[x] def groups(self) -> list: """ グループ構造の詳細を返す Return ------ res:list[] グループ構造を返す """ member = [[] for _ in range(len(self.par))] for v in range(len(self.par)): member[self.root(v)].append(v) res = [] for mem in member: if mem: res.append(mem) return res from collections import defaultdict N, M = map(int, input().split()) C = list(map(int, input().split())) UF = UnionFind(N) colors = defaultdict(int) for _ in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 if C[u] == C[v]: UF.unite(u, v) for v in range(N): if v == UF.root(v): colors[C[v]] += 1 ans = sum([v - 1 for v in colors.values()]) print(ans)