陶瓷小猫(Ceramic kitten)

题目描述
想了想自己家里的那套陶瓷小猫,因在外头摆了十一年,表面的光泽已大不如前,趁着这个契机去给那套重新上釉,倒是不错。

如果这样的话,不妨照着LCT的这套去上色吧。

小戾家中的小猫摆件与LCT家的,都由N个小猫构成。由于每只小猫形态各异,它们各能获得一个唯一的编号。

小戾清楚,自家的第i只小猫被涂成了\(c_i\)色(\(c_i\)不同表示颜色不同,\(c_i\)相同表示颜色相同),他于是想要记住LCT家小猫们的颜色。

奈何小戾并不是记忆大师,他无法记住所有的具体颜色。当他回到家中时,脑海中剩下的只有M条信息,第i条遵循如下结构:

LCT家第\(x_i\)只小猫和第\(y_i\)只小猫颜色相同。
小戾想知道,他最少需要把家中的多少只小猫重新涂色,才能使得重新涂色后的陶瓷小猫们满足所有的这M条LCT家小猫摆件的描述。这样的方案显然存在。

输入格式
第一行两个数\(N,M\),分别表示一套陶瓷小猫中小猫的个数与信息的条数。

接下来一行\(N\)个数,第i个数\(c_i\),表示小戾家第i只小猫的颜色。

接下来M行,每行两个数\(x_i,y_i\)。表示在LCT家的第xi只与第yi只小猫颜色相同。

保证\(1≤x_i,y_i≤N\)。

输出格式
一个数,表示在最优方案下,需要重新涂色的小猫数量。

样例输入1

3 3
1 3 1 
1 1
1 1
2 3

样例输出1

1

样例输入2

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

样例输出2

2

题目限制
时间限制:1000ms

空间限制:512MB

对于30%的数据,\(N,M≤5\)。

对于50%的数据,\(N,M,ci≤100\)。

对于70%的数据,\(N,M≤10^3\)。

对于80%的数据,\(c_i≤10^5\)。

对于100%的数据,\(N,M≤10^5,0<c_i≤10^9, 1≤x_i,y_i≤N\)。

看到这种谁和谁相等的信息,想到了并查集。

用并查集合并完之后,对于每一个连通块,那么这个连通块至少需要涂的数量就是连通块大小减连通块中出现次数次数的颜色的数量。现在研究怎样统计并找到出现次数最多的颜色。

首先颜色我们可以通过离散化让他全部在n以内。然后用vector记录每一个并查集都有那些小猫,在每一个连通块中去统计即可。注意统计的数组不要每次都memset,可以考虑每次统计完后把有改变的颜色清零。

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