并查集

并查集 (Union-Find Sets) 是一种简单而用途广泛的高级数据结构

并查集可以描述这样一个逻辑结构：有若干个元素，将其分成若干个不相交的集合，每个集合相互独立

使用并查集可以方便地进行以下两种操作：

      1.判断两个元素是否属于同一个集合

      2.合并两个元素所在的集合

并查集机构的储存结构为一棵采用双亲表示法的树，通常用数组来储存。每个元素还有权值：

#define MAX 1000 struct Union_Find_Sets { int parent; int rank; }set[MAX];

其中parent的值为正数时，表示该节点的父节点的下标值，为负数时表示该节点为根节点，其负数的绝对值为该集合包含节点的个数

rank则为权值，在不同的情况下有不同的含义，由程序员自己来决定

对于并查集主要有以下三种操作

//初始化并查集 void MakeSet() { int i; for (i = 0; i < MAX; i ++) { //初始阶段每个节点单独构成一个集合 set[i].parent = -1; //权值的初始值视具体情况而定 set[i].rank = 0; } } //查找包含节点x的集合的根节点，返回其下标 int FindSet(int x) { int i, tmp; for (i = x; set[i].parent >= 0; i = set[i].parent); //压缩路径，提高以后的查找效率 while (i != x) { tmp = set[x].parent; //把搜索路径上所有节点的父节点都直接改为根节点 set[x].parent = i; x = tmp; } return i; } //合并a和b所在的集合 void Union(int a, int b) { int fa, fb; fa = FindSet(a); fb = FindSet(b); //a和b已经在同一集合 if (fa == fb) return; //将较小的集合变为较大的集合的子集 if (set[fa].parent < set[fb].parent) { set[fa].parent += set[fb].parent; set[fb].parent = fa; } else { set[fb].parent += set[fa].parent; set[fa].parent = fb; } }