CC

自然万物都趋向从有序变得无序

0%

How Many Tables HDU - 1213

发表于 更新于 分类于 Valine：

题目链接:点我

题目

 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

题意:

某个人要过生日,相识或者间接认识的人要坐在一起,问需要多少张桌子,

思路:

并查集(维基百科),并查集的基础应用,我们把认识的人用并查集维护,将他们指向同一个祖先即可,

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;

int f[1000+10];

int getf(int x){
    if(x == f[x])
        return x;
    return f[x] = getf(f[x]);//路径压缩,
}

void Merge(int x, int y){把两个人指向同一个祖先,
    int t1 = getf(x);
    int t2 = getf(y);
    if( t1 != t2){
        f[t1] = t2;
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n, m;
        scanf("%d %d", &n, &m);
        for(int  i = 1; i <= n; ++i)
            f[i] = i;
        while(m--){
            int x, y;
            scanf("%d %d", &x, &y);
            Merge(x,y);
        }
        int ans = 0;
        for(int i = 1; i <= n; ++i)
            if(f[i] == i)//最后指向自己的人就是分成的份数
                ++ans;
        printf("%d\n",ans);
    }
    return 0;
}