# 陶瓷小猫(Ceramic kitten)-其他

## 陶瓷小猫(Ceramic kitten)

LCT家第\(x_i\)只小猫和第\(y_i\)只小猫颜色相同。

``````3 3
1 3 1
1 1
1 1
2 3
``````

``````1
``````

``````5 5
3 5 3 2 4
1 5
3 5
3 2
3 2
5 2
``````

``````2
``````

``````#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,c[N],lsh[N],x,y,fa[N],ret,ans,t[N],cnt[N];
vector<int>g[N];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",c+i),lsh[i]=c[i],fa[i]=i;
sort(lsh+1,lsh+n+1);
for(int i=1;i<=n;i++)
c[i]=lower_bound(lsh+1,lsh+n+1,c[i])-lsh;
while(m--)
scanf("%d%d",&x,&y),fa[find(x)]=find(y);
for(int i=1;i<=n;i++)
g[find(i)].push_back(i),t[find(i)]++;
for(int i=1;i<=n;i++)
{
if(fa[i]==i)
{
for(int j=0;j<g[i].size();j++)
cnt[c[g[i][j]]]++;
ret=0;
for(int j=0;j<g[i].size();j++)
ret=max(ret,cnt[c[g[i][j]]]);
ans+=t[i]-ret;
for(int j=0;j<g[i].size();j++)
cnt[c[g[i][j]]]=0;
}
}
printf("%d",ans);
return 0;
}
``````
————————

Title Description
After thinking about the ceramic kitten in my home, because it has been outside for 11 years, the gloss of the surface is much worse than before. It’s good to take this opportunity to re glaze the set.

If so, you might as well paint according to the LCT.

Kitten ornaments in Xiaoli’s home and LCT’s are composed of N kittens. Because each kitten has different shapes, they can get a unique number.

Xiao Li knew that his ith kitten was painted with \ (c_i \) color (\ (c_i \) means different colors, and \ (c_i \) means the same color), so he wanted to remember the colors of LCT kittens.

However, Xiao Li is not a memory master. He can’t remember all the specific colors. When he returned home, there were only m pieces of information left in his mind, and article I followed the following structure:

The \ (x_i \) kitten of LCT family is the same color as the \ (y_i \) kitten.
Xiao Li wants to know how many kittens he needs to recolor at least in order to make the recolored ceramic kittens meet all the descriptions of LCT kitten ornaments. Such a scheme obviously exists.

Input format
Two numbers \ (n, m \) in the first line represent the number of kittens in a set of ceramic kittens and the number of messages.

The next line \ (n \) number and the ith number \ (c_i \) represent the color of the ith kitten in Xiaoli’s family.

Next M lines, two numbers per line \ (x_i, y_i \). It means that the Xi kitten in LCT’s home is the same color as the Yi kitten.

Guarantee \ (1 ≤ x_i, y_i ≤ n \).

Output format
A number that represents the number of kittens that need to be recolored under the optimal scheme.

Sample input 1

``````3 3
1 3 1
1 1
1 1
2 3
``````

Sample output 1

``````1
``````

Sample input 2

``````5 5
3 5 3 2 4
1 5
3 5
3 2
3 2
5 2
``````

Sample output 2

``````2
``````

Topic limitation
Time limit: 1000ms

Space limit: 512MB

For 30% of the data, \ (n, m ≤ 5 \).

For 50% of the data, \ (n, m, CI ≤ 100 \).

For 70% of the data, \ (n, m ≤ 10 ^ 3 \).

For 80% of the data, \ (c_i ≤ 10 ^ 5 \).

For 100% data, \ (n, m ≤ 10 ^ 5,0 & lt; c_i ≤ 10 ^ 9, 1 ≤ x_i, y_i ≤ n \).

Seeing this kind of information about who is equal to who, I thought of and looked up the set.

After using and checking the set and merging, for each connected block, the minimum number of connected blocks to be painted is the size of connected blocks minus the number of colors in connected blocks. Now study how to count and find the most frequent colors.

First of all, we can discretize the color to make it all within n. Then use vector to record each kitten and look up the kittens in each connected block. Note that the statistical array should not be memset every time. You can consider clearing the changed color after each statistics.

``````#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,c[N],lsh[N],x,y,fa[N],ret,ans,t[N],cnt[N];
vector<int>g[N];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",c+i),lsh[i]=c[i],fa[i]=i;
sort(lsh+1,lsh+n+1);
for(int i=1;i<=n;i++)
c[i]=lower_bound(lsh+1,lsh+n+1,c[i])-lsh;
while(m--)
scanf("%d%d",&x,&y),fa[find(x)]=find(y);
for(int i=1;i<=n;i++)
g[find(i)].push_back(i),t[find(i)]++;
for(int i=1;i<=n;i++)
{
if(fa[i]==i)
{
for(int j=0;j<g[i].size();j++)
cnt[c[g[i][j]]]++;
ret=0;
for(int j=0;j<g[i].size();j++)
ret=max(ret,cnt[c[g[i][j]]]);
ans+=t[i]-ret;
for(int j=0;j<g[i].size();j++)
cnt[c[g[i][j]]]=0;
}
}
printf("%d",ans);
return 0;
}
``````