并查集

题目点这里

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const	int N=200010;
int p[N];
int c[N];
int num[N];
vector<int>v[N];
int find(int x)
{
   
	if(x!=p[x])
	p[x]=find(p[x]);
	return p[x];
}
int main()
{
   
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	cin>>c[i];
	for(int i=1;i<=n;i++)
	p[i]=i;
	while(m--)
	{
   
		int l,r;
		cin>>l>>r;
		p[find(l)]=find(r);
	}
	int  tot=0;
	for(int i=1;i<=n;i++)
	if(p[i]==i)	num[i]=++tot;
	for(int i=1;i<=n;i++)
	v[num[find(i)]].push_back(c[i]);//这里find(i)目的是为了保持同个集合里在二维v数组里同一行，方便统计相同颜色的个数 
	int ans=0;//答案 
	for(int i=1;i<=tot;i++)
	{
   
		int s=v[i].size();//集合中袜子的个数 
		int mx=0;
		map<int,int>mp;
		for(int j=0;j<s;j++)
		{
   
			mp[v[i][j]]++;
			mx=max(mx,mp[v[i][j]]);	//找出一个集合中颜色相同最多的 
		}
		ans+=(s-mx);//只需要把颜色不同的染成最多相同颜色的就行了 
	}
	printf("%d\n",ans);
	return 0;
}