結果
問題 | No.2563 色ごとのグループ |
ユーザー |
|
提出日時 | 2023-12-02 15:16:30 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 734 ms / 2,000 ms |
コード長 | 2,603 bytes |
コンパイル時間 | 4,635 ms |
コンパイル使用メモリ | 173,444 KB |
実行使用メモリ | 125,600 KB |
最終ジャッジ日時 | 2024-09-26 18:21:57 |
合計ジャッジ時間 | 13,800 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import std;void main () {/*色ごとの全域木をつくるかんじで辞書型UFでずるする*/int N, M; readln.read(N, M);int[] C = readln.split.to!(int[]);alias UFarr = UnionFind_Dictionary!(int);UFarr[int] UF;foreach (c; C) UF[c] = UnionFind_Any!(int);// 登録foreach (i, c; C) UF[c].addElement(cast(int) i);foreach (i; 0..M) {int u, v; readln.read(u, v);u--, v--;if (C[u] == C[v]) {UF[C[u]].unite(u, v);}}int ans = 0;foreach (U; UF) {ans += U.countGroups-1;}writeln(ans);}void read (T...) (string S, ref T args) {auto buf = S.split;foreach (i, ref arg; args) {arg = buf[i].to!(typeof(arg));}}class UnionFind_Dictionary (T) {private:T[T] parent;int[T] size;T root (T x) {if (x !in parent) {addElement(x);return x;}if (parent[x] == x) return x;return parent[x] = root(parent[x]);}bool same (T x, T y) {return root(x) == root(y);}void unite (T x, T y) {addElement(x), addElement(y);T larger, smaller;if (GroupSize(x) <= GroupSize(y)) {larger = root(y);smaller = root(x);} else {larger = root(x);smaller = root(y);}if (larger == smaller) return;parent[smaller] = larger;size[larger] += size[smaller];}int countGroups () {int res = 0;foreach (key, val; parent) {if (root(key) == key) res++;}return res;}bool addElement (T x) {if (x in parent) return false;parent[x] = x;size[x] = 1;return true;}int GroupSize (T x) {addElement(x);return size[root(x)];}T[][] enumGroups (T x) {T[][T] mp;T[][] res;foreach (key, val; parent) {mp[root(key)] ~= key;}foreach (val; mp) {res ~= val;}return res;}void reset () {parent.clear;size.clear;}}auto UnionFind_Any (T) () {return new UnionFind_Dictionary!(T)();}import std.range.primitives : isInputRange;auto UnionFind_Any (T, E) (E range) if (isInputRange!(E) || is(T == S[], S) || is(T == S[n], S, size_t n)) {auto res = new UnionFind_Dictionary!(T)();foreach (elem; range) {res.addElement(elem);}return res;}