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.

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.

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

2
5 3
1 2
2 3
4 5

5 1
2 5

2
4

Ignatius.L

Eddy

 

 

 

 

#include<stdio.h>
#include<string.h>
int town[1002];   //存储朋友关系情况，并查集根节点
int n,m;
int find(int x)     //查找根节点
{
    while(x != town[x]) //该节点非根节点，寻找根节点
        x = town[x];
        //若该节点为根节点，直接返回该节点值
    return x;
}
void union1(int a,int b)    //将a，b两个集合连接合并为一个集合(可能本来为同一集合)
{
    int a_f=find(a),b_f=find(b);    //分别查找两个集合的根节点
    if(a_f!=b_f)    //若根节点不同，即为不同集合，则合并两个集合
        town[b_f]=a_f;
}
int main()
{
    int i,j,k;
    int a,b;
    int sum[1002];  //记录每个人朋友关系集合的根节点
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(town,0,sizeof(town[0])*(n+1));   //存储结构初始化
        memset(sum,0,sizeof(sum[0])*(n+1));
        for(i=1;i<=n;i++)   //未知朋友关系时，每个节点为一个集合，其根节点为其本身
            town[i]=i;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            union1(a,b);    //得知a，b是朋友后，将a，b两个集合合并
        }
        for(i=1; i<=n; i++) //统一每个集合的根节点，使同一个集合根节点相同
            town[i] = find(town[i]);
        for(i=1;i<=n;i++)   //统计个人作为作为根节点的情况（遍历城镇连通情况表）
            sum[town[i]]=1;
        int x=0;
        for(i=1;i<=n;i++)   //统计根节点个数（非朋友集合个数）
            x+=sum[i];
        printf("%d\n",x);
    }
    return 0;
}