本文共 1725 字，大约阅读时间需要 5 分钟。
所谓并查集，就是集合，对集合的操作分为两种：并和查。
下面有两种实现。 第一种是不进行任何改善的。 第二种是进行改善的。#include#include typedef int ElemntType;//采用数组存储方式，根的parent为-1.typedef struct{ ElemntType Data; int parent;}SetType;//findint Find(SetType S[], ElemntType X){ /*在数组S中查找为x的元素所属的集合*/ /*MaxSize为数组S的最大长度*/ int i; for (i = 0; i < Maxsize&&S[i].Data != X; i++);/*每次都要再去找，麻烦！*/ if (i >= Maxsize)return -1; /*未找到X，返回-1*/ for (; S[i].parent >= 0; i = S[i].parent); return i;/*找到X所属集合，返回树根节点在数组S中的下标*/}void Union(SetType S[], ElementType X1, ElemntType X2){ int Root1, Root2; Root1 = Find(S, X1); Root2 = Find(S, X2); if (Root1 != Root2)S[Root2].parent = Root1;}
#include#include using namespace std;#define MAXN 1000 /* 集合最大元素个数 */ typedef int ElementType; /* 默认元素可以用非负整数表示 */typedef int SetName; /* 默认用根结点的下标作为集合名称 */typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 *//*按秩归并，前者是按照规模，后者按照树高，建议用前者，因为路径压缩的时候树高会发生变化，而进行路径压缩的时候并没有修改树高*/void Union(SetType S, SetName Root1, SetName Root2 ) //S[Root]=-元素数{ /* 这里默认Root1和Root2是不同集合的根结点 */ /* 保证小集合并入大集合 */ if (S[Root2] < S[Root1]) { /* 如果集合2比较大 */ S[Root2] += S[Root1]; /* 集合1并入集合2 */ S[Root1] = Root2; } else { /* 如果集合1比较大 */ S[Root1] += S[Root2]; /* 集合2并入集合1 */ S[Root2] = Root1; }}void Union(SetType S, SetName Root1, SetName Root2)//S[Root]=-树高{ if (S[Root1] > S[Root2])//h1
//非递归查找int Find(int x){ int k, j, r; r = x; while (s[r] >= 0)r = s[r]; //找根节点,r记录 k = x; while (k != r) //非递归路径压缩 { j = s[k]; s[k] = r; k = j; } return r;} 转载地址：http://bkyci.baihongyu.com/