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

o
osc_z1hvg4cu

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

### osc_z1hvg4cu

#### 暂无文章

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

osc_dh3qbz0a
1分钟前
0
0

osc_kvlhvh2u
2分钟前
0
0

osc_z3ivsxnp
4分钟前
0
0

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

osc_zken4nb1
5分钟前
0
0

osc_b67rw1ne
7分钟前
0
0