HDU 1213

简介: How Many Table                               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

How Many Table                              

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


 #include"stdio.h"
int p[1000];
int find(int x)
{
    int k, j, r;
          r = x;
    while(r != p[r])
        r = p[r];
    k = x;
    while(k != r)
    {
        j = p[k];
        p[k] = r;
        k = j;
    }
    return r;
}
int main()
{
    int m,n,i,j;
    int t;
      scanf("%d",&t);
    while(t--)
    {
     scanf("%d",&m);
            int sum,x,y;
          sum=m;
           for( i=0;i<=m;i++)
             p[i]=i;
             scanf("%d",&n);
          while(n--)
        {          scanf("%d%d",&x,&y);
              if(find(x)!=find(y))
           {
                  p[find(y)]=find(x);
                     sum--;
           }
         }
             printf("%d\n",sum);
            getchar();
    }
    return 0;
}


  

目录
相关文章
|
机器学习/深度学习
|
测试技术 Java
|
人工智能 BI Java
HDU 1003
Max Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 105228    Accepted Submission(s): 242...
897 0
|
Java 测试技术
HDU 1847
Good Luck in CET-4 Everybody! Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3204    Accepted Submission(s): 2008 Problem Description 大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。
854 0
|
Java
HDU 1846(巴什博弈)
Brave Game Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4050    Accepted Submission(s): 2644 Problem Description 十年前读大学的时候,中国每年都要从国外引进一些电影大片,其中有一部电影就叫《勇敢者的游戏》(英文名称:Zathura),一直到现在,我依然对于电影中的部分电脑特技印象深刻。
794 0
|
机器学习/深度学习
hdu1059Dividing
题意:有6种石头,价值分别是1,2,3,4,5,6   每种有若干,作为输入数据。问能否把这些石头按照价值均分? 分析:多重背包问题。 代码: View Code 1 #include 2 #include 3 #include 4 using namespace...
873 0