結果

問題 No.2563 色ごとのグループ
コンテスト
ユーザー Hydrogen332
提出日時 2026-01-22 00:23:59
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 73 ms / 2,000 ms
コード長 1,022 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,701 ms
コンパイル使用メモリ 337,972 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-22 00:24:07
合計ジャッジ時間 7,001 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, e) for (int i = (int)(s); i < (int)(e); ++i)

struct UnionFind {
	vector<int> par;
	int group;
	
	UnionFind(int N) : par(N, -1), group(N) {}
	
	int root(int x) {
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}
	
	bool merge(int x, int y) {
		if ((x = root(x)) == (y = root(y))) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		--group;
		return true;
	}
	
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	
	int size(int x) {
		return -par[root(x)];
	}
};

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	
	int N, M;
	cin >> N >> M;
	vector<int> C(N), cnt(N);
	rep(i, 0, N) {
		cin >> C[i];
		++cnt[C[i] - 1];
	}
	
	int ans = 0;
	rep(i, 0, N) ans += max(cnt[i] - 1, 0);
	
	UnionFind uf(N);
	
	rep(i, 0, M) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		if (C[u] == C[v] && !uf.same(u, v)) {
			uf.merge(u, v);
			--ans;
		}
	}
	
	cout << ans << '\n';
}
0