Description

有\(n\)只襪子，\(k\)種顏色，在\(m\)天中，問(wèn)最少修改幾只襪子的顏色，可以使每天要穿的襪子顏色相同。

Input

第一行\(n,m,k\)分別對(duì)應(yīng)題目描述。

接下來(lái)\(m\)行每行兩個(gè)整數(shù)\(l_i，r_i\)表示第\(i\)天要穿的兩只襪子的編號(hào)。

Output

一個(gè)整數(shù),代表最小要修改幾只襪子的顏色。

首先,對(duì)于每一天要穿的襪子,我們加入同一個(gè)并查集。(這個(gè)很明顯吧)

如果有一只襪子需要被穿多次的話,

顯然我們會(huì)將其染成當(dāng)前聯(lián)通塊中包含襪子最多的一種顏色。

我們用\(vector\)維護(hù)每個(gè)聯(lián)通塊中的襪子的顏色。

再開(kāi)\(vis\)數(shù)組維護(hù)每種襪子的出現(xiàn)次數(shù)。(注意要清空)

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

其中\(size\)為聯(lián)通塊大小,\(mx\)為顏色相同的最多的襪子的個(gè)數(shù)。

代碼

#include<cstdio> #include<algorithm> #include<vector> #include<iostream> #define R registerusing 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); }

轉(zhuǎn)載于:https://www.cnblogs.com/-guz/p/9909338.html

總結(jié)

以上是生活随笔為你收集整理的并查集【CF731C】Socks的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。