How Many Tables

2
5 3
1 2
2 3
4 5

5 1
2 5

2
4

Recommend

代码不是很长，可是我理解了很久很久，也不知道自己的理解是不是对的。反正分享一下。。

5 3

1 2

2 3

4 5

2

这个案例代表有编号为1到5的五个人， 三代表有三对朋友，下面分别代表1和2是朋友，2和3是朋友，4和5是朋友。。 输出2代表两张桌子。因为1和2是朋友，2和3是朋友，默认1和3也是朋友。所以三个人只要一张桌子。4和5一张桌子就够了。题目的意思就是这个。给你一个编号n，下面列出m对人的关系，问你最少需要准备多少张桌子。一个多月前我就做过这道题，那时很天真，随便想了个方法，结果了WA了，还跑去讨论区问别人（丢脸）。

以前天真的代码。。

现在我附上我所理解的代码。不知道有没理解错的。

#include <stdio.h>
int p[1005];
int find(int x)     //这个的作用就是下面的查找。
{ 
	if(x!=p[x])
		p[x]=find(p[x]);
	return p[x];
}
int hebing(int x,int y)  //这个的作用就是用来合并的。
{
	return  p[x]=y;     //假设a=2,b=3，此时应该有p[2]=p[3]=3。即2和3到同一张桌子了。
}
int main()
{
    int t,i,a,b;
	scanf("%d",&t);
	while(t--)
	{
		int n,m,ans=0;
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)
			p[i]=i;   //初始化它，让编号为一的值为1，编号为2的值为2.以此类推。
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			a=find(a);   
			b=find(b);   //假设a=2,b=3,我认为经过这个查找之后p[2]就等于p[3]了。
			if(a!=b)
				hebing(a,b);  //合并为一个值。
		}
		for(i=1;i<=n;i++)
		{
			if(p[i]==i)   //经过M次合并之后，如果是朋友，或者间接朋友的，他们对应的值都为同一个。所以桌子就减少了。
				ans++;     //如果值还是对应的，那么就不是朋友关系，增加一张桌子。
		}
		printf("%d\n",ans);//输出注意格式，只有一个空行。
	}
	return 0;
}

HDU 1213 How Many Tables 第一道并查集的题。