HDU1213 How many tables
2023-02-18 16:34:30 时间
HDU1213 How many tables
问题描述
今天是依纳爵(Ignatius)的生日。他邀请了很多朋友。现在是晚饭时间。伊格内修斯想知道他至少需要多少张桌子。您必须注意,并不是所有的朋友都彼此认识,并且所有的朋友都不想和陌生人呆在一起。
解决此问题的一条重要规则是,如果我告诉您A认识B,而B认识C,则意味着A,B,C彼此认识,因此它们可以呆在一张桌子上。
例如:如果我告诉你A知道B,B知道C,D知道E,那么A,B,C可以留在一个表中,而D,E必须留在另一个表中。因此,伊格纳修斯至少需要2张桌子。
输入项:
输入以整数T(1 <= T <= 25)开头,该整数表示测试用例的数量。然后是T测试用例。每个测试用例均以两个整数N和M(1 <= N,M <= 1000)开头。N表示朋友的数量,朋友从1到N标记。然后跟随M行。每行包含两个整数A和B(A!= B),这意味着朋友A和朋友B彼此认识。两种情况之间将有一个空白行。
输出量:
对于每个测试用例,只需输出Ignatius至少需要多少个表。请勿打印任何空白。
样本输入
2
5 3
1 2
2 3
4 5
5 1
2 5
样本输出
2
4
#include<iostream>
#include<bits/stdc++.h>
const int max_size=1000;
using namespace std;
int pre[max_size];
void init_set(int count){
for (int i = 1; i <= count; i++)
{
pre[i]=i;
}
}
int find_set(int x){
return x==pre[x]?x:find_set(pre[x]);
}
void union_set(int x,int y){
x =find_set(x);
y=find_set(y);
if(x!=y) pre[x]=pre[y];
}
int main(){
int n;
cin>>n;
int a,b,c,d;
while (n--)
{
cin>>a>>b;
init_set(a);
for (int i = 1; i <= b; i++)
{
cin>>c>>d;
union_set(c,d);
}
int ans=0;
for (int i = 1; i <= a; i++)
{
if (pre[i]==i)
ans++;
}
cout<<ans<<endl;
}
}
相关文章
- 数据库优化方法 (一)
- 水晶报表钻取数据,在明细层导的时候,报表会从新加载,并显示主报表
- [MySQL] mysql中实现统计每日数量
- [MySQL] group_concat多行数据合并到一行方便取出来进行in查询
- 验证视图状态 MAC 失败的解决办法
- [MySQL] 解决mysql导出excel数值型变成科学计数法问题
- [转] SQL Server 2005索引碎片整理SQL语句
- [转]gridview获取当前行索引的方法
- [日常] 电脑上输入emoji🤔表情方法
- 数据库系统的维护与优化(二)
- 数据库系统的维护与优化(一)
- sql server 2005中的Service broker小示例(未完善)
- sql server 错误9003:LSN无效(日志扫描号无效),对数据库的修复.
- sqlserver注入方式与安全防护的学习
- [PHP] laravel中collect数组排序和过滤的使用
- SQL Server 2005的DML触发器分After触发器的研究
- sql server 2005商业智能的初步了解(1)
- [日常]UserAgent中的AhrefsBot解释
- sql server 存储过程中使用变量表,临时表的分析(续)
- 物流信息系统开发与设计(四)