# Hdoj 1213 How Many Tables 【并查集】

How Many Tables

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 16590 Accepted Submission(s): 8117

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

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
const int M = 1e3+5;
const int INF = 0x3f3f3f3f;
const int N = 2e6+5;
using namespace std;

int fat[M];
bool vis[M];

int f(int x){
if(x != fat[x]) fat[x] = f(fat[x]);
return fat[x];
}

int main(){
int t, n, m;
scanf("%d", &t);
while(t --){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i) fat[i] = i;
int a, b;
for(int i = 0; i < m; ++ i){
scanf("%d%d", &a, &b);
int x = f(a); int y = f(b);
if(x != y) fat[x] = y;
}
int ans = 0;
for(int i = 1; i <= n; ++ i)
if(fat[i] == i) ++ans;
printf("%d\n", ans);
}
return 0;
}``````

## HDU 1213 How Many Tables (并查集)

How Many Tables Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 1213 Appoint description:  System Crawler  (2015-05-25) Description Today is Ignatius' birthday. He invites a lot of friends. Now

## HDU 1213 How Many Tables (并查集，常规) ## HDU 1213 How Many Tables (并查集,连通分支数,两种方式)

How Many Tables Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 23012    Accepted Submission(s): 11485 Problem Description Today is Ignatius' birthday. He invites a lot of friends. Now it's din

## hdu1213 How Many Tables(并查集)

How Many Tables Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17946    Accepted Submission(s): 8822 Problem Description Today is Ignatius' birthday. He invites a lot of friends. Now it's dinn

## hdoj 2473 Junk-Mail Filter【并查集节点的删除】

Junk-Mail Filter Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7515    Accepted Submission(s): 2368 Problem Description Recognizing junk mails is a tough task. The method used here consists o

## hdoj 1213 How Many Tables

How Many Tables Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 16616    Accepted Submission(s): 8137 Problem Description Today is Ignatius' birthday. He invites a lot of friends. Now it's dinne