并查集【CF731C】Socks

Description

有\(n\)只袜子，\(k\)种颜色，在\(m\)天中，问最少修改几只袜子的颜色，可以使每天要穿的袜子颜色相同。

Input

第一行\(n,m,k\)分别对应题目描述。

接下来\(m\)行每行两个整数\(l_i，r_i\)表示第\(i\)天要穿的两只袜子的编号。

Output

一个整数,代表最小要修改几只袜子的颜色。

首先,对于每一天要穿的袜子,我们加入同一个并查集。(这个很明显吧)

如果有一只袜子需要被穿多次的话,

显然我们会将其染成当前联通块中包含袜子最多的一种颜色。

我们用\(vector\)维护每个联通块中的袜子的颜色。

再开\(vis\)数组维护每种袜子的出现次数。(注意要清空)

每次我们累加的答案就是\(size-mx\)

其中\(size\)为联通块大小,\(mx\)为颜色相同的最多的袜子的个数。

代码

#include<cstdio>

#include<algorithm>

#include<vector>

#include<iostream>

#define R register

using namespace std;

const int gz=200001;

inline void in(R int &x)

{

    int f=1;x=0;char s=getchar();

    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

    while(isdigit(s)){x=x*10+s-'0';s=getchar();}

    x*=f;

}

vector<int>v[gz];

int col[gz],f[gz],n,m,k,ans,vis[gz];

int find(R int x){return f[x]==x?x:f[x]=find(f[x]);}

signed main()

{

    in(n),in(m),in(k);

    for(R int i=1;i<=n;i++)in(col[i]),f[i]=i;

    for(R int i=1,x,y;i<=m;i++)

    {

        in(x),in(y);

        R int fa=find(x),fb=find(y);

        if(fa==fb)continue;

        f[fa]=fb;

    }

    for(R int i=1;i<=n;i++)

    {

        R int fa=find(i);

        v[fa].push_back(col[i]);

    }

    for(R int i=1;i<=n;i++)

    {

        R int tmp=v[i].size();

        R int mx=0;

        if(tmp>1)

        {

            for(R int j=0;j<tmp;j++)

            {

                vis[v[i][j]]++;

                mx=max(mx,vis[v[i][j]]);

            }

            for(R int j=0;j<tmp;j++)

                vis[v[i][j]]--;

            ans+=tmp-mx;

        }

    }

    printf("%d",ans);

}

巴特西

并查集【CF731C】Socks

Description

Input

Output

最新文章

热门文章