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;
}
时间: 04-16

Hdoj 1213 How Many Tables 【并查集】的相关文章

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 (并查集,常规)

并查集基本知识看:http://blog.csdn.net/dellaserss/article/details/7724401 题意:假设一张桌子可坐无限多人,小明准备邀请一些朋友来,所有有关系的朋友都可以坐同一张桌,没有关系的则要另开一桌,问需要多少张桌子(小明不坐,不考虑小明与其他人的关系)? 思路:常规的并查集.要求出所有人的老大,有几个老大就要几张桌子.那么有关系的都归为同一个老大.用数组实现,再顺便压缩路径. 1 #include <bits/stdc++.h> 2 #define

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

hdu 1213 求连通分量(并查集模板题)

求连通分量 Sample Input2 //T5 3 //n m1 2// u v2 34 5 5 12 5 Sample Output24 1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <algorithm> 5 # include <cmath> 6 # include <queue> 7 # define LL long

hdoj 3635 Dragon Balls【并查集求节点转移次数+节点数+某点根节点】

Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4384    Accepted Submission(s): 1673 Problem Description Five hundred years later, the number of dragon balls will increase unexpecte

hdoj 1878 欧拉回路(无向图欧拉回路+并查集)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1878 思路分析:该问题给定一个无向图,要求判断该无向图是否存在欧拉回路:无向图判断存在欧拉回路的两个必要条件:该无向图为连通图且所有的结点的度数为偶数: 代码如下: #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MAX_N = 1000 + 10