文档章节

HDU 1213 - How Many Tables - [并查集模板题]

o
 osc_z1hvg4cu
发布于 2018/04/24 19:31
字数 621
阅读 16
收藏 0
par

行业解决方案、产品招募中!想赚钱就来传!>>>

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1213

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<bits/stdc++.h>
using namespace std;
const int maxn=1000+5;

int n,m;

int par[maxn],ran[maxn];
void init(int l,int r){for(int i=l;i<=r;i++) par[i]=i,ran[i]=0;}
int find(int x){return (par[x]==x)?x:(par[x]=find(par[x]));}
void unite(int x,int y)
{
    x=find(x), y=find(y);
    if(x==y) return;
    if(ran[x]<ran[y]) par[x]=y;
    else par[y]=x, ran[x]+=(ran[x]==ran[y]);
}
bool isSame(int x,int y){return find(x)==find(y);}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);

        init(1,n);
        for(int i=1,a,b;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            if(!isSame(a,b)) unite(a,b);
        }

        set<int> S;
        for(int i=1;i<=n;i++) S.insert(find(i));

        printf("%d\n",S.size());
    }
}

 

整理一下并查集的两种模板吧:

int par[maxn],ran[maxn];
void init(int l,int r){for(int i=l;i<=r;i++) par[i]=i,ran[i]=0;}
int find(int x){return (par[x]==x)?x:(par[x]=find(par[x]));}
void unite(int x,int y)
{
    x=find(x), y=find(y);
    if(x==y) return;
    if(ran[x]<ran[y]) par[x]=y;
    else par[y]=x, ran[x]+=(ran[x]==ran[y]);
}
bool isSame(int x,int y){return find(x)==find(y);}
int par[maxn];
void init(int l,int r){for(int i=l;i<=r;i++) par[i]=i;}
int find(int x){return (par[x]==x)?x:(par[x]=find(par[x]));}

//这种简单的并查集的合并方式是:
int t1=find(u),t2=find(v);
if(t1!=t2) par[t1]=t2; //这种是把点u所在树并入点v所在树
if(t1!=t2) par[t2]=t1; //这种是把点v所在树并入点u所在树

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

基于反射实现DBUtils封装(读取数据库数据生成对象或对象集合以及对数据库的CRUD)version2.0

DBUtils version2.0 附带jdbc.properties配置文件 支持操作: 1.加载驱动 2.获取数据库连接对象 3.关闭资源 4.封装通用的更新操作:INSERT UPDATE DELETE 5.封装通用查询单条数据的方法 (JDB...

osc_dh3qbz0a
1分钟前
0
0
标准驼峰命名转数据库字段

碰到一个这样的场景,数据库字段bill_no 代表单据编号,然后返回前端json 是billNo,严格按照驼峰命名法,现在前端需要自定义按照箭头进行排序,但是并不知道数据库字段,所以前端只能给你"...

osc_kvlhvh2u
2分钟前
0
0
突然的立秋

前几天在某app上面耍到说“8月7号就立秋了,等我们再见面就该穿长袖了,不,我们应该不会再见到了”。 就很突然了,今天立秋了。 秋天到了,和夏天的人和事好好道个别吧。 还记得以前,每年的...

osc_z3ivsxnp
4分钟前
0
0
第一届华数杯A题思路分析

** 华数杯a题浅见 需要本文的话请加2574364134 ** 当我刚拿到这个题目的时候,惊呆了,这个不就是2018年国赛的A题吗?2018年的国赛A题是为了进行高温防护,这道题现在就是低温防护服御寒,所...

osc_zken4nb1
5分钟前
0
0
想象自己在前方等自己-纯内心戏

以下为一年级某个时刻的痛苦挣扎,就是个经历而已,记录经历。 论文的初初稿终于在昨天发给了老师。客观的讲我写的真的很差,很多时候感觉自己写不下去了,很多放弃的念头不是一闪而过,而是...

osc_b67rw1ne
7分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部