数据结构与算法（4）——并查集
并查集
维护一些不相交的集合，它是一个集合的集合。每个元素恰好属于一个集合，好比每条鱼装在一个鱼缸里。每个集合S有一个元素作为集合代表"rep[S]，好比每个鱼缸选出一条"鱼王"。并查集提供三种操作：
MakeSet(x)：建立一个新集合x。x应该不在现有的任何一个集合中出现。
Find(S, x)：返回x所在集合的代表元素。
Union(x, y)：把x所在的集合和y所在的集合合并。森林表示法
可以用一棵森林表示并查集，森林里的每棵树表示一个集合，树根就是集合的代表元素。一个集合还可以用很多种树表示，只要树中的结点不变，表示的都是同一个集合。
合并操作
只需要将一棵树的根设为另一棵即可。这一步显然是常数的。一个优化是：把小的树合并到大树中，这样会让深度不太大。这个优化称为启发式合并.
查找操作
只需要不断的找父亲，根就是集合代表。一个优化是把沿途上所有结点的父亲改成根。这一步是顺便的，不增加时间复杂度，却使得今后的操作比较快。这个优化称为路径压缩。
下面是最基本得并查集代码，牢记，用得多了，写这种常用数据结构应该做到倒背如流，才可应对ACM中出现的各种变形 ！！！
const int SIZE = 100;
int p[SIZE],rank_deep[SIZE];
//rank_deep[]记录该集合的深度//可以根据题目设置不同意义的rank数组
void makeset(int x){
p[x] = x;
rank_deep[x] = 0;
}
//非递归的方式进行路径压缩，更加直观一些
int findSet(int x){
int px = x,i;
//find root
while(px!=p[px])px = p[px];
//path compression
while(x != px){
i=p[x];
p[x]=px;
x=i;
}
return px;
}
void unionSet(int x,int y){
x = findSet(x);
y = findSet(y);
//原则：小的接到大的后面
if(rank_deep[x]>rank_deep[y])
p[y]=x;
else{
p[x]=y;
//deep的定义为多分枝的最远那一条
if(rank_deep[x]==rank_deep[y])rank_deep[y]++;
}
}实际应用：
POJ-1611 http://poj.org/problem?id=1611
/*并查集的基本应用——POJ1611*/
/************************************************************************
大致题意：一共有n个学生(编号0 至 n-1)，m个组，一个学生可以同时加入不同的组。
现在有一种传染病，如果一个学生被感染，那么和他同组的学生都会被感染。现在已
知0号学生被感染，问一共有多少个人被感染。
首先将每个学生都初始化为一个集合，然后将同组的学生合并，设置一个数组num[]
来记录每个集合中元素的个数，最后只要输出0号学生所在集合中元素的个数即可。
**************************************************************************/
#include<iostream>
usingnamespace std;
//num[]数组存储节点所在的集合的总个数
//father[]数组存储dina
int num[30001],father[30001];
//初始化用，把每一个点定义为一个集合
void makeSet(int x){
father[x]=x;//定义跟节点的标志：即为与父亲数组的值相同
num[x]=1;
}
/*补充：综合编程 , 其他综合 ,上一个：从一个Perl程序看网络服务器设计
下一个：数据结构与算法（3）——二叉堆CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，
