L - Socks

并查集的思路題

題意：

有 n隻襪子，k種顔色（沒啥用),需要穿m天，每天都要穿相同顔色的襪子，已知每隻襪子的顔色，求最少需要染幾隻襪子

題解：

有m天每天都穿一雙襪子,我們先把這雙襪子加到一個集合U,在把這個集合指向一個顔色點color,再計算這個集合中相同襪子的最大數量，剩餘的就是需要染色的襪子

講解集合：

這裡為什麼要用集合呢，因為題目已經滿足每天穿的襪子，是以每一個集合的顔色需要一樣，然後從每一個集合中找到需要染的色

#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
int pre[maxn];
int color[maxn];
vector<int>vec[maxn];//建立一個容器
int find(int x)//查找
{
    if(x!=pre[x])
    {
        pre[x]=find(pre[x]);
    }
    return pre[x];
}
void join(int x,int y)//合并為一個集合
{
    int boss1=find(x);
    int boss2=find(y);
    if(boss1!=boss2)
    {
        pre[boss2]=boss1;
    }
}
int main()
{
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
        scanf("%d",&color[i]);//每隻襪子的顔色
    }
    int u,v;
    while(m--)
    {
        scanf("%d %d",&u,&v);
        join(u,v);//把要穿的一雙襪子加入集合
    }
    for(int i=1;i<=n;i++)
    {
        vec[find(i)].push_back(color[i]);//将和i一個集合的襪子指向color[i]
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        map<int,int>temp;//因為數可能很大,是以需要用map處理後的數組離散化處理
                         //直接開數組無法離散化處理
        int maxx=0;
        for(int j=0;j<vec[i].size();j++)
        {
            temp[vec[i][j]]++;//map開的數組自動初始化,清空
            maxx=max(maxx,temp[vec[i][j]]);
        }
        ans+=vec[i].size()-maxx;//一個集合中顔色不相同的襪子數量需要染色

    }
    printf("%d\n",ans);

}