当前位置：首页 > article >正文

算法学习021 c++有多少张桌子并查集算法学习中小学算法思维学习比赛算法题解信奥算法解析

article 2024/9/27 10:07:47

C++有多少张桌子

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、运行结果

五、考点分析

六、推荐资料

C++有多少张桌子

一、题目要求

1、编程实现

今天是小明的生日。他邀请了很多朋友。现在是晚餐时间。小明想知道他至少需要多少张桌子。你必须注意到，不是所有的朋友都互相认识，而并不是所有的朋友都想和陌生人呆在一起。

这个问题的一个重要规则是，如果我告诉你 A 认识 B，B 认识 C，那就意味着 A、B、C 互相认识，所以他们可以呆在一张桌子上。不考虑一张桌子能做多少人，问需要多少张桌子。

例如：如果我告诉你 A 认识 B，B 认识 C，D 认识 E，所以 A、B、C 可以呆在一张桌子上，而 D、E 必须呆在另一张桌子上。所以小明至少需要 2 张桌子。

2、输入输出

输入描述：输入两个整数N和M(1<=N,M<=1000)开头，N表示好友数，好友从1到N依次标记，后面跟着M行，每行两个整数A和B(A!=B)，表示好友A和好友B互相认识。

输出描述：输出小明至少需要多少张桌子。不要打印任何空白。

输入样例：

输出样例：

二、算法分析

从给定题目的初步分析可以看出，这是一个比较典型的并查集的案例
并查集（Disjoint-Set）是一种数据结构，用于管理一组不相交的集合。通常用于解决一些关于集合划分、节点连通性、图的连通分量、等价关系等问题
既然这是一个并查集的案例，而并查集的实现其实可以分成三步：初始化、查找和合并
初始化：开始可以将每一个人（节点）对应一个集合
查找：根据每个人（节点）查找他所在的集合，然后返回该节点或者该集合
合并：将两个人（节点）分别查找是否在同一个集合，如果在不用做任何操作，如果不在，将其中一个人的集合改为另一个人所在的集合
最后只需要遍历所有的人（节点），如果人（节点）跟他所对应的集合相等，则说明找到一个集合，也就是我们题目对应的桌子

三、程序编写

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int s[N];//集合 

//初始化集合 
void init_set(int n)
{
	for(int i=0;i<n;i++)
		s[i] = i;
}
//查找元素是否在集合（递归方式） 
int find_set(int x)
{
	return x==s[x]?x:find_set(s[x]); //最基础的写法，如果相等也就是根节点，返回自己，否则返回上一级
//	if(x != s[x]) s[x] = find_set(s[x]); //优化：路径压缩，如果查找的节点不是跟节点，就将所有的节点的父节点改为根节点，方便下次查询 
//	return s[x];
}

//合并集合
void union_set(int x,int y) 
{
	x = find_set(x);//找到x的父节点 
	y = find_set(y);//找到y的父节点 
	if(x != y) s[x] = s[y];//合并根节点 
}

int main()
{
	int n,m,res = 0; //res统计桌子数量 
	cin >> n >> m;
	init_set(n);
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin >> a >> b;
		union_set(a,b);
	} 
	
	for(int i=0;i<n;i++)
		if(s[i] == i)
			res++;
	cout << res << endl;
	return 0; 
}

本文作者：小兔子编程作者首页：小兔子编程-CSDN博客