题目：
链接：点击打开链接
题意：
有n个朋友，编号为1......n。知道其中一些人相互认识，求最少需要多少桌子。
算法：
并查集算法的模板题。
(来源：LCY-teacher课件)
>>在某个城市里住着n个人，现在给定关于 n个人的m条信息（即某2个人认识）假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？
>>如何实现？
>>什么是并查集？
>>英文：Disjoint Set，即“不相交集合”将编号分别为1…N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。常见两种操作：I.合并两个集合.II.查找某元素属于哪个集合
>>.........
思路：
代码：
#include#include #include using namespace std; int n,m,a,b,cnt; int father[1010]; int getfather(int n) { while(n != father[n]) n = father[n]; return n; } void Union(int x,int y) { int rootx = getfather(x); int rooty = getfather(y); if(rootx != rooty) father[rooty] = rootx; } int main() { //freopen("input.txt","r",stdin); int t; cin>>t; while(t--) { getchar(); cnt = 0; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) father[i] = i; for(int i=1; i<=m; i++) { scanf("%d%d",&a,&b); Union(a,b); } for(int i=1; i<=n; i++) { if(father[i] == i) cnt++; } printf("%d\n",cnt); } return 0; }