How Many Tables HDU - 1213
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.
InputThe 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. 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.
OutputFor 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 5Sample Output
2 4
思路：意思就是求有几颗树，一开始WA了一个地方，一定要注意，下面看代码，我会注释。
#include <stdio.h>
int n,pair; //代表有n个人,pair对关系
int parent[1005];
int res;
int find(int x) // 寻找根节点用压缩路径，可以节省时间
{
return (x==parent[x])?x:parent[x]=find(parent[x]);
}
void unite(int x,int y) // 作用：合并两个集合
{
x=find(x);
y=find(y);
if(x!=y) // 这里被坑了，如果不加x!=y 就会wa。因为不加就会出现多减的情况，例如1与2,3有关系构成了一个树，如果4与2有关系，4与3有关系，就会多减了1，所以要判断根节点是否相同，在有些题里不用判断，但这题要判断。还是思维不严密。
{
parent[x]=y;
res--;
}
}
void init() // 将每个节点都作为父节点，其实就是分成n个集合，每个集合只有1个节点，自然也是父亲节点
{
scanf("%d%d",&n,&pair);
res=n;
for(int i=1;i<=n;i++)
parent[i]=i;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
init();
for(int i=1;i<=pair;i++)
{
int num1,num2;
scanf("%d%d",&num1,&num2);
unite(num1,num2);
}
printf("%d\n",res);
}
}
查看8道真题和解析