(并查集)Socks CF-731C

题意：k种颜色，n只袜子，m次的要求两只袜子颜色相同，问最小改变袜子颜色使得两只袜子颜色相同的操作次数
题解：一开始想只用并查集做，最后直接输出入集次数，但是这样做等于将整个颜色集合直接混入另一种。
正解：计算每个联通块中最大颜色重复数，分别用联通块里袜子总数减去最大重复数，最后加起来就是答案。
所以我们可以选择用邻接表与标记数组来做，用（map初始化默认为0，数组存不下）map来储存c[i]出现的次数。
或者可以选择并查集压缩连接，然后递推出mx数组，最后用n减去每个mx[i]的值。
代码1：

 #include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+9;
int n,m,k,a[MAX],mx,cnt=0,ans=0,mark[MAX];
map<int,int> mp;
vector<int> g[MAX];
void dfs(int v)
{
    mp[a[v]]++,cnt++,mark[v]=1;
    mx=max(mp[a[v]],mx);
    for (auto u:g[v]) if (!mark[u]) dfs(u);
}
int main()
{
    cin>>n>>m>>k;
    for (int i=0;i<n;i++) cin>>a[i];
    for (int i=0,v,u;i<m;i++) cin>>v>>u,v--,u--,g[v].push_back(u),g[u].push_back(v);
    for (int i=0;i<n;i++) if (!mark[i]) mp.clear(),mx=0,cnt=0,dfs(i),ans+=cnt-mx;
    cout<<ans;
}

代码2：

#include <bits/stdc++.h>
using namespace std;
const int N=200100;
int n,m,k,x,y,v[N],fa[N],mx[N],ans;
map<int,int> mp[N];
inline int ask(int x)
{
    return fa[x]==x?x:fa[x]=ask(fa[x]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]),fa[i]=i;
    for(int i=1;i<=m;++i)
    scanf("%d%d",&x,&y),fa[ask(x)]=ask(y);
    for(int i=1;i<=n;++i)
    mx[ask(i)]=max(mx[ask(i)],++mp[ask(i)][v[i]]);
    ans=n;
    for(int i=1;i<=n;++i)
    ans-=mx[i];
    printf("%d",ans);
    return 0;
}