本文主要是介绍HDU ACM 1213.How Many Tables（简单的 并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/**********************************
题目大意：把是朋友的人放到一组，n个人可以分成几组，并输出组数；
题目解析：运用并查集把有关系的人合并到一组，最后遍历数组father[i],查看i根结点是否为他自己；
错误分析：1. 最主要的是题目已经知道总人数，应该把总人数运用参数传递给初始化的函数init()2.定义 n,i,x,y;不能定义为全局变量，否则不能输出结果，至于为什么我也不懂，求解？
*********************************/
#include<cstdio>
#include<iostream>
using namespace std;
#define M 1005
int father[M],rank[M];
//father[i]为i的父结点，rank[i]为i所属集合的总元素数
void init(int n)
//初始化,注意此时的函数init（）有参数传递
{int i;for(i=1;i<=n;i++){father[i]=i;// 各个元素独自构成一个集合rank[i]=1;}
}
int find(int x)
//查找根结点
{if(x!=father[x])father[x]=find(father[x]);// 压缩路径，减少查询时运行的时间，使结点都指向根结点return father[x];
}
void Union(int x,int y)
// 合并
{x=find(x);//查找x的根结点y=find(y);if(x!=y)//若两个x,y的根结点不同（即两个元素不再一个集合中），则合并两个集合{father[x]=y;rank[y]+=rank[x];}}int main()
{int n,m,i,x,y,t,rank1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init(n);rank1=0;while(m--){scanf("%d %d",&x,&y);Union(x,y);}for(i=1;i<=n;i++)//遍历数组，找出有多少个子集合{if(father[i]==i)rank1++;}printf("%d\n",rank1);}return 0;
}
这篇关于HDU ACM 1213.How Many Tables（简单的 并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
