C++数据结构——热闹的聚会

news/2024/7/15 17:20:38 标签: c++, 数据结构, 图论

热闹的聚会

今天是小明的生日,他邀请了许多朋友参加聚会,当然,有些朋友之间由于互不认识,因此不愿意坐在同一张桌上,但是如果A认识B,且B认识C,那么A和C就算是认识的。
为了使得聚会更加热闹,就应该尽可能少用桌子。那么,最热闹(人数最多的)的那一桌一共有多少人吗?

输入格式:

首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据首先输入2个整数n和m (1≤n , m≤1000)。其中n表示朋友总数,并且编号从1到n;然后输入m行数据,每行2个整数A和 B (A≠B), 表示朋友A和B相互认识。

输出格式:

对于每组测试,输出最热闹的那一桌的总人数。

输入样例:
3
5 3
1 2
2 3
4 5
5 1
2 5
10 9
7 8
1 5
1 7
1 2
1 3
1 4
2 6
2 9
9 2
输出样例:
3
2
9

代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

解题代码

#include<bits/stdc++.h>
using namespace std;
int men[1005];
int ans[1005];
int find(int x)
{
	if(men[x]==x){
		return men[x];
	} 
	men[x]=find(men[x]);
	return men[x];
}

void Union(int a,int b)	//合并 
{
	a = find(a);
	b = find(b);
	if(a!=b){
		men[b]=a;
		ans[a]+=ans[b];
	}
}

int main()
{
	int T,n,m,a,b;
	cin>>T;
    
	while(T--){
		cin>>n>>m;;
		for(int i=1;i<=n;i++){
			men[i]=i;
			ans[i]=1;
		}
		for(int i=0;i<m;i++){
			cin>>a>>b;
			Union(a,b);
		}
		int maxNum = 0;
		for(int i=1;i<=n;i++){
			if(ans[i]>maxNum&&men[i]==i)
			maxNum=ans[i];
		}
		cout<<maxNum<<endl;
	} 
} 

解题思路
并查集,这里要每次合并的时候,要把一边的数量存储到新合并上的一边,一开始用指针提交pta爆段错误,离谱


http://www.niftyadmin.cn/n/1483338.html

相关文章

python+selenium+chromewebdriver或Firefox的环境搭建

插件下载地址 chromewebdriver&#xff1a;https://chromedriver.storage.googleapis.com/index.html?path2.26/放置在python下的Scripts Firefox下载地址&#xff1a;https://github.com/mozilla/geckodriver/releases放在python里和上面一样 转载于:https://www.cnblogs.com…

c++基于对象的编程风格2

知识点&#xff1a; 1.iterator的定义 inline Triangular_iterator& Triangular_iterator:: operator() { // prefix instance_index;check_integrity();return *this; } 前置版本返回的对象的引用&#xff0c;目的是提高效率&#xff0c;此函数通俗讲就是直接加返回…

memcache 客户端性能对比试验

http://xmemcached.googlecode.com/svn/trunk/benchmark/benchmark.html

C++数据结构——统计二叉树的叶结点个数

统计二叉树的叶结点个数 根据带虚结点的先序序列建立二叉树&#xff0c;计算其叶子结点的数目后输出。 输入格式: 测试数据有多组&#xff0c;处理到文件尾。每组测试数据在一行中输入一个字符串&#xff08;不含空格且长度不超过80&#xff09;&#xff0c;表示二叉树的先序遍…

Objective-C中的一些特殊的数据类及NSLog的输出格式

NSLog的格式如下所示&#xff1a; % 对象%d, %i 整数%u 无符整形%f 浮点/双字%x, %X 二进制整数%o 八进制整数%zu size_t%p 指针%e 浮点/双字 &#xff08;科学计算&#xff09;%g 浮点/双字 %s C 字符串%.*s Pascal字符串%c 字符%C …

跌跌撞撞我也进入了STM32的大门

今天开始我开始写我的CSDN博客了&#xff0c;之前学C的时候也零零散散写过几篇&#xff0c;但都是玩儿&#xff0c;太随意了&#xff0c;这次我要坚持下去&#xff0c;或许一年后或几年后我还会回来看看&#xff0c;希望到那时我会发现“嗨我真的进步了不少哈&#xff01;”博客…

oracle存储过程的简单学习2

1.选用何种游标? 显示游标分为&#xff1a;普通游标&#xff0c;参数化游标和游标变量三种。 create or replace procedure proc(p varchar2)asv_rownum number(10) : 1;cursor c1 is select ename from emp where rownum 1;cursor c2 is select ename from emp where rownum…

libbpf 开发指南:根据给定的名称查找 BPF 程序类型和期望的附加类型

目录 函数原型与解释 代码demo makefile cmake 期望输出 函数原型与解释 LIBBPF_API int libbpf_prog_type_by_name(const char *name, enum bpf_prog_type *prog_type, enum bpf_attach_type *expected_attach_type); 参数解释&#xff1a; name&#xff1a;表示 BPF …