首页 > 代码库 > 725C
725C
找出连通块,然后找出颜色最大的,用总数减去
#include<iostream>
#include<map>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
vector<int>graph[200010];
int n,m,k,ans,temp,tot;
map<int,int>color;
int use[200010],a[200010],used[200010];
inline void dfs(int u)
{
used[u]=1;
tot++;
for(int i=0;i<graph[u].size();i++)
{
int v=graph[u][i];
if(!used[v]) color[a[v]]++;
if(color[a[v]]>temp) temp=color[a[v]];
if(!used[v]) dfs(v);
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
use[l]=1;
use[r]=1;
graph[l].push_back(r);
graph[r].push_back(l);
}
for(int i=1;i<=n;i++)
{
if(!used[i]&&use[i])
{
tot=0;
temp=0;
color.clear();
color[a[i]]++;
dfs(i);
ans+=tot-temp;
}
}
cout<<ans<<endl;
return 0;
}
725C