HDU 1213 How Many Tables(并查集讲解)
HDU 1213 How Many Tables(并查集讲解)
这是我写的第一道并查集的题，也应该是一道最简单的入门题了，所以就以这道题说下并查集，其实就是找关系，比如说这道题的题意就是有n个人聚餐，然后他们不一定都互相认识，如果a认识b，b认识c，那么就让他们仨坐一桌，再如果c认识d，d认识e，那么就让这三个人另外坐一桌，所以就是有关系的就坐一桌，然后问需要多少张桌子(忽略每张桌子能坐多少人)。
那么并查集就分为并和查两个过程， 首先我们需要开一个数组pre来记录，刚开始我们初始化为pre[i] = i，然后在输入数据的时候将他们有关系的都并起来，比如输入1和2，2和3，我们可以先查这些点的是不是独立的结点，如果是的话就把他们连起来，那么就是pre[2]=1,pre[3]=2，这里可以用一个路径压缩，来把3号的父节点改成1，这样更便于查找(压缩路径下面会说)，那么现在就是pre[2]=1,pre[3]=1，这就是并的过程，而查的过程就是比如说你要查3号，然后pre[3]就是3号对应的根节点了。思路大概是这样的，具体的东西可以结合代码看一下。
并查集呢也就是并和查两个部分，所以用两个函数Merge和Find(我习惯这么定义了)，而查的过程中有很多种写法，可以用循环，也可以用递归，我看其他Dalao的博客写的都很详细，我也没有那么好的文采，所以这里就不详细的说了。先说一下没有路径压缩的写法，虽然路径压缩可以大大减短运行时间，但是有时候有些题它不压缩路径才能做。思路就是在一个while循环里不断的去查当前节点的父节点，直到x==pre[x]为止，最后的r就是你要查的x的根节点了。
int Find(int x){
int r=x;
while(parent[r] !=r)
r=parent[r];
return r;
}然后说一下路径压缩的方法，路径压缩可以缩短程序运行时间，方法也分为递归方法和非递归方法，而递归方法有时候对于数据较大的程序来说会造成栈溢出，所以对于这种情况可以用非递归的方法，不太好理解，试着手动模拟一下就很好理解了。
int Find(int x){ // 非递归方法
int k, j, r;
r = x;
while(r != parent[r]) // 查找跟节点
r = parent[r]; // 找到跟节点，用r记录下
k = x;
while(k != r){
j = parent[k]; // 用j暂存parent[k]的父节点
parent[k] = r; // parent[x]指向跟节点
k = j; // k移到父节点
}
return r;
}
int Find(int x){ // 递归方法
if(x != pre[x]){
pre[x] = Find(pre[x]);
}
return pre[x];
}然后是并的过程。
void merge(int x,int y){
int fx = Find(x); // 查找x的根节点
int fy = Find(y); // 查找y的根节点
if(fx != fy){
pre[fy] = fx; // 合并
}
}最后看一下开头说的那道题的代码吧，还不理解的就手动模拟一下。
AC代码：
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1005;
int pre[MAXN];
int T,n,m;
void init(){
for(int i=0;i<=n;i++){
pre[i] = i;
}
}
int Find(int x){
if(x != pre[x]){
pre[x] = Find(pre[x]);
}
return pre[x];
}
void merge(int x,int y){
int fx = Find(x);
int fy = Find(y);
if(fx != fy){
pre[fy] = fx;
}
}
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
merge(a,b);
}
int sum = 0;
for(int i=1;i<=n;i++){
if(i == pre[i]){
sum++;
}
}
printf("%d\n",sum);
}
return 0;
}