How Many Tables（并查集）

How Many Tables

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

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

   题意：

   有T（1到25）个Case，每个Case首先有N个人（1到1000）和M（1到1000）对朋友关系，如果a和b是朋友，b和c是朋友，那么a和c也算是朋友。规定同是朋友的可以坐在同一桌台上，不是朋友的则不能，问最少需要有多少张台。

   思路：

   并查集基础题。先把每个人都分别算为一个独立的集合，然后再根据给出的朋友关系合并到同一个集合中，最后算一共有几个集合即可。

AC：

#include<stdio.h>
#include<string.h>
int main()
{
	int t;
	int set[1005];
//代表每个人属于哪个集合
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		int sum=0;
		scanf("%d%d",&n,&m);
		memset(set,0,sizeof(set));
		for(int i=1;i<=n;i++)
		   set[i]=i;
//每个人独立为一个集合
		while(m--)
		{
			int a,b;
			int x,y;
			scanf("%d%d",&a,&b);
			x=set[a];
			y=set[b];
			if(x==y) continue;
//如果属于同一个集合则不需合并
			if(x>y)	 
			{
			 for(int j=1;j<=n;j++)
			  if(set[j]==x)  set[j]=y;
		        }
			if(x<y)  
			{
			 for(int j=1;j<=n;j++)
			  if(set[j]==y)  set[j]=x;
			}
//如果不属于同一个集合则合并，将处于集合更大的序数合并到小的序号中
		}
		for(int i=1;i<=n;i++)
		 if(set[i]==i) sum++;
//每个集合都以小序号的名字命名
//所以当集合名与本身序数一样，说明为一个新的集合
		printf("%d\n",sum);
	}
	return 0;
}

小改进:

#include<stdio.h>
#include<string.h>
int main()
{
	int t;
	int set[1005];
	scanf("%d",&t);
	while(t--)
	{
		int n,m,sum;
		scanf("%d%d",&n,&m);
		memset(set,0,sizeof(set));
		for(int i=1;i<=n;i++)
		  set[i]=i;
		sum=0;
		while(m--)
		{
			int a,b;
			int min,max,temp;
			scanf("%d%d",&a,&b);
			min=set[a];
			max=set[b];
			if(min==max) continue;
//主要是这段
			if(min>max)
			{
				temp=min;
				min=max;
				max=temp;
			}
			for(int i=1;i<=n;i++)
			  if(set[i]==max) set[i]=min;
//合并不是同一集合的元素
		}
		for(int i=1;i<=n;i++)
		 if(set[i]==i) sum++;
		printf("%d\n",sum);
	}
	return 0;
}

总结：

   一开始还以为有多难，原理不难懂，关键是敲代码。敲得太少，加上畏难心理，拖延浪费了不少时间。