HDU 1213 How Many Tables 第一道並查集的題。

How Many Tables

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15083 Accepted Submission(s): 7361


Problem Description Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input

2
5 3
1 2
2 3
4 5

5 1
2 5

Sample Output

2
4

Author Ignatius.L
Source 杭電ACM省賽集訓隊選拔賽之熱身賽

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