$$\color{Purple}{kuangbin题解目录}$$
描述
今天是伊格内修斯的生日,他邀请了 $N$ 个朋友来参加他的生日宴会。
这 $N$ 个人的编号为 $1 \\sim N$。
现在,晚餐时间到了,他需要安排朋友们上桌吃饭。
并不是所有人都互相认识,他们当中存在 $M$ 对两两认识关系。
在本题中,我们认为这种关系是具有传递性的,也就是说如果 $A$ 和 $B$ 认识,$B$ 和 $C$ 认识,则 $A,B,C$ 都彼此认识。
这 $N$ 个人都不希望和陌生人在同一桌吃饭。
请问,伊格内修斯至少需要准备多少张桌子。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $N,M$。
接下来 $M$ 行,每行包含两个整数 $a,b$,表示 $a$ 和 $b$ 彼此认识。
相邻两组数据之间由一行空行隔开。
输出格式
每组数据输出一行结果,一个整数表示最少需要的桌子数量。
数据范围
$1 \\le T \\le 25$,
$1 \\le N,M \\le 1000$,
$1 \\le a,b \\le N$,
$a \\neq b$。
输入样例:
2
5 3
1 2
2 3
4 5
5 1
2 5
输出样例:
2
4
思路
- 利用
并查集
解决,将认识的人放入一个集合中,最后检查fa[i]==i
集合的根元素的个数即为所求.
代码
// Problem: 多少张桌子
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4288/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-27 20:03:16
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 1010
using namespace std;
typedef long long ll;
int t,n,m;
int fa[MAXN];
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
cin >> n >> m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
int a,b;
cin >> a >> b;
int fx=find(a),fy=find(b);
if(fx!=fy)
fa[fx]=fy;
}
int res=0;
for(int i=1;i<=n;i++)
if(fa[i]==i)
res++;
cout << res << endl;
}
return 0;
}