不相交集合(Disjoint-set )数据结构保持一组不相交的动态集合S={S(1),S(2),…,S(k)}.每个集合通过一个代表（representative）来识别，即集合中的某个成员。设x表示一个对象，不相交集合支持操作：
MAKE-SET(x):建立一个新的结合，其唯一成员（也即代表）就是x。因为各集合是不相交的，故要求x没有在其他集合中出现过。
UNION(x,y):将包含x和y的动态集合合并成一个新的集合（即这两个集合的并集）。假定在这个操作之前两个集合是不相交的，操作之后，选取集合S(x)或S(y)的代表作为新代表。
FIND-SET(x):返回一个指向包含x的（唯一）集合的代表
不相交集合数据结构的一个应用：
确定一个无向图连通子图的个数。过程如下：
下面过程CONNECTED-COMPONENTS利用不相交集合操作来计算一个图的连通子图：
一旦CONNECTED-COMPONETS作为预处理步骤执行后，，SAME-COMPONENT判断两个顶点是否在同一连通子图中：
不相交集合的链表表示
如合并的操作中，一种简单的操作方式是采用链表集合表示来实现，如下图：
利用链表结构实现上述应用的完整代码如下：
#include<iostream>#include<string>#include<cstdlib>#include<vector>#define N 256using namespace std;typedef struct setNode{char key;setNode *next;setNode *representative;setNode(char k):key(k),next(NULL),representative(NULL){}}setNode;typedef struct Set{int num;setNode *head;setNode *tail;}Set;typedef struct edge{char u;char v;}edge;Set Make_Set(char k){setNode *x=new setNode(k);Set *s = new Set();s->head = x;s->tail = x;s->num = 1;x->representative = x;return *s;}setNode *Find_Set(Set s){return s.head->representative;}void Update_Representative(setNode *head, setNode *representative){setNode *p=head;while(p != NULL){ p->representative = representative;p = p->next; }}void PrintSet(Set x){setNode *p = x.head;while(p != NULL){cout<<p->key<<" ";p = p->next; }cout<<endl;}void Print_conComponents(Set LinklistSet[],int n){int count=1;for(int i=0; i<n; i++)if(LinklistSet[i].num != 0){cout<<"Connect component "<<count<<" is:";PrintSet(LinklistSet[i]);count++;}} void Set_Union(Set &x,Set &y){ if (x.num < y.num){ Set temp;temp = x;x = y;y = temp;}Update_Representative(y.head, x.head);x.tail->next = y.head;x.tail = y.tail;x.num += y.num;y.num =0;}void LinklistSet_Create(Set LinklistSet[],char vertex[],int vNum){for(int i=0;i<vNum;i++){int index=(int)vertex[i];//eg.a->97,b->98,…LinklistSet[index] = Make_Set(vertex[i]); } }void Compute_conComponents(Set LinklistSet[],edge edgeArray[],int eNum){//Compute the component forestfor(int i=0;i<eNum;i++){Set *set_u = &LinklistSet[(int)edgeArray[i].u]; //use the pointer to change the LinklistSet[] infoSet *set_v = &LinklistSet[(int)edgeArray[i].v];if (Find_Set(*set_u) != Find_Set(*set_v)){//Set_Union(LinklistSet[(int)edgeArray[i].u],LinklistSet[(int)edgeArray[i].v]);Set_Union(*set_u,*set_v);}}}int main(){char vertex[]={'a','b','c','d','e','f','g','h','i','j'};edge edgeArray[]={{'b','d'},{'e','g'},{'a','c'},{'h','i'},{'a','b'},{'e','f'},{'b','c'}};int vNum=sizeof(vertex)/sizeof(char);int eNum=sizeof(edgeArray)/sizeof(edge);Set LinklistSet[N]={NULL};LinklistSet_Create(LinklistSet,vertex,vNum);//link list set createCompute_conComponents(LinklistSet,edgeArray,eNum);Print_conComponents(LinklistSet,N);return 0;}运行结果：
【注：若有错误，请指点~~~~】
版权声明：本文为博主原创文章，未经博主允许不得转载。
在人生的道路上，谁都会遇到困难和挫折，
