HDUOJ---1213How Many Tables
2024-09-24 08:42:01
How Many Tables
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9828 Accepted Submission(s): 4872
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.
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
Author
Ignatius.L
Source
代码:
并查集,模板的运用..
#include<stdio.h>
#include<string.h>
#define maxn 1005
int father[maxn+],rank[maxn+]; /*³õʼ»¯*/
void init(int n)
{
for(int i=;i<=n;i++)
{
father[i]=i;
rank[i]=;
}
} /*²é*/
int setfind(int x)
{
if(father[x]==x)
return x;
return setfind(father[x]);
} /*²¢*/
void Union(int a,int b)
{
int x=setfind(a);
int y=setfind(b);
if(x!=y)
{
if(rank[x]>rank[y])
{
father[y]=x;
rank[x]+=rank[y];
}
else
{
father[x]=y;
rank[y]+=rank[x];
}
}
} int main()
{
int t,m,n,i,a,b;
/* freopen("test.in","r",stdin); freopen("test.out","w",stdout);
*/
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init(n);
for(i=;i<m;i++)
{
scanf("%d%d",&a,&b);
Union(a,b);
}
int cnt=;
for(i=;i<=n;i++)
if(father[i]==i)
cnt++;
printf("%d\n",cnt);
}
return ;
}
最新文章
- 淌水 UE4的shootergame 案例 准备
- wget: unable to resolve host address的解决方法
- XAMPP PHP redis 扩展
- Wince 对话框程序设计
- A Tour of Go Exercise: Slices
- 李洪强iOS开发本人集成环信的经验总结_01环信SDK的导入
- Host group 信息
- [avalon]data-repeat-rendered循环渲染完毕后的回调函数
- ctrl+z 以后怎么恢复挂起的进程
- [ Java学习基础 ] Java对象的创建和销毁
- 【!Important】如何保证线程执行的先后顺序
- 16 级高代 II 思考题九的七种解法
- Python基础-使用paramiko
- js添加select中option
- 【转】JS浮点数运算Bug的解决办法
- 三星平板SM-T320刷机
- HDU1874畅通project续 dijkstra&;amp;&;amp;floyd
- HDUOJ----4504 威威猫系列故事——篮球梦
- WINDOWS常用端口列表
- 图解Sysprep封装系统