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 ;
}