#934250 (D) No.2563 色ごとのグループ

• 問題: No.2563 色ごとのグループ
• ユーザー: k82b
• 提出日時: 2023-12-02 15:04:42
• 言語: D (dmd 2.106.1)
• 結果: AC
• 実行時間: 362 ms / 2,000 ms
• コード長: 1,309 bytes
• コンパイル時間: 3,128 ms
• コンパイル使用メモリ: 163,316 KB
• 実行使用メモリ: 30,304 KB
• 最終ジャッジ日時: 2023-12-02 15:04:51
• 合計ジャッジ時間: 8,960 ms
• ジャッジサーバーID （参考情報）: judge9 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,676 KB
testcase_01	AC	1 ms; 6,676 KB
testcase_02	AC	1 ms; 6,676 KB
testcase_03	AC	1 ms; 6,676 KB
testcase_04	AC	1 ms; 6,676 KB
testcase_05	AC	1 ms; 6,676 KB
testcase_06	AC	1 ms; 6,676 KB
testcase_07	AC	1 ms; 6,676 KB
testcase_08	AC	1 ms; 6,676 KB
testcase_09	AC	2 ms; 6,676 KB
testcase_10	AC	2 ms; 6,676 KB
testcase_11	AC	2 ms; 6,676 KB
testcase_12	AC	1 ms; 6,676 KB
testcase_13	AC	1 ms; 6,676 KB
testcase_14	AC	3 ms; 6,676 KB
testcase_15	AC	4 ms; 6,676 KB
testcase_16	AC	3 ms; 6,676 KB
testcase_17	AC	3 ms; 6,676 KB
testcase_18	AC	2 ms; 6,676 KB
testcase_19	AC	9 ms; 6,676 KB
testcase_20	AC	18 ms; 6,676 KB
testcase_21	AC	12 ms; 6,676 KB
testcase_22	AC	11 ms; 6,676 KB
testcase_23	AC	21 ms; 6,676 KB
testcase_24	AC	194 ms; 14,820 KB
testcase_25	AC	150 ms; 15,140 KB
testcase_26	AC	209 ms; 20,944 KB
testcase_27	AC	171 ms; 25,336 KB
testcase_28	AC	247 ms; 21,352 KB
testcase_29	AC	348 ms; 30,304 KB
testcase_30	AC	341 ms; 30,304 KB
testcase_31	AC	362 ms; 30,304 KB
testcase_32	AC	339 ms; 30,304 KB
testcase_33	AC	312 ms; 30,304 KB
testcase_34	AC	325 ms; 30,304 KB
testcase_35	AC	339 ms; 30,304 KB
testcase_36	AC	311 ms; 30,304 KB
testcase_37	AC	324 ms; 30,304 KB

ソースコード

import std, core.bitop;
string[] _R;
void readM(T)(ref T x) { while (_R.empty) { _R = readln.chomp.split; } x = _R.front.to!T; _R.popFront; }
bool chmin(T)(ref T A, T B) { if (A > B) { A = B; return true; } else { return false; } }
bool chmax(T)(ref T A, T B) { if (A < B) { A = B; return true; } else { return false; } }
int lowerBound(T)(T[] A, T x) { int lo = -1, hi = cast(int)(A.length); while (hi - lo > 1) { int mid = lo + hi >> 1; (A[mid] < x ? lo : hi) = mid; } return hi; }
int upperBound(T)(T[] A, T x) { int lo = -1, hi = cast(int)(A.length); while (hi - lo > 1) { int mid = lo + hi >> 1; (A[mid] > x ? hi : lo) = mid; } return hi; }

void main() {
	int N, M;
	N.readM;
	M.readM;
	auto C = new int[N];
	foreach (i; 0 .. N) {
		C[i].readM;
	}
	auto G = new int[][](N, 0);
	foreach (i; 0 .. M) {
		int u, v;
		u.readM;
		v.readM;
		--u, --v;
		G[u] ~= v;
		G[v] ~= u;
	}
	int ans;
	auto A = new int[N];
	auto vis = new bool[N];
	foreach (i; 0 .. N) {
		if (!vis[i]) {
			++A[C[i] - 1];
			int[] que;
			que ~= i;
			vis[i] = true;
			while (!que.empty) {
				int u = que.front;
				que.popFront;
				foreach (v; G[u]) {
					if (C[u] == C[v] && !vis[v]) {
						vis[v] = true;
						que ~= v;
					}
				}
			}
		}
	}
	foreach (i; 0 .. N) {
		if (A[i]) {
			ans += A[i] - 1;
		}
	}
	writeln(ans);
}