Codeforces 731C 并查集

题意：给出n只袜子的，最多k个颜色，m天，每天都要穿某两只袜子，不能让某一天穿不同颜色的袜子，问至少改变多少只袜子的颜色。

思路：把在同一天穿的袜子用并查集放到一起，然后找出最多的那种颜色，size-max即为这堆袜子至少要改的次数。

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
typedef long long LL;
typedef unsigned long long ULL;

const int maxn=;
int ans;
int n,m,k;
int c[maxn];
int l,r;
int F[maxn];
vector<int>v[maxn];
int Find(int x){
    return x==F[x]?x:F[x]=Find(F[x]);
}
void Union(int a,int b){
    int t1=Find(a);
    int t2=Find(b);
    if(t1!=t2){
        F[t1]=t2;
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=;i<=n;i++){
        scanf("%d",c+i);
        F[i]=i;
    }
    for(int i=;i<=m;i++){
        scanf("%d%d",&l,&r);
        Union(l,r);
    }
    ans=;
    for(int i=;i<=n;i++){
        v[Find(i)].push_back(c[i]);
    }
    for(int i=;i<=n;i++){
        if(v[i].size()<=)continue ;
        int sz=,MX=;
        map<int,int>mp;
        for(int j=;j<v[i].size();j++){
            mp[v[i][j]]++;
            MX=max(MX,mp[v[i][j]]);
            sz++;
        }
        ans+=sz-MX;
    }
    printf("%d\n",ans);
    return ;
}