分析其他-并查集

并查集◆并查集是一种树型的数据结构，用于处理一些不相交集合S={S1,S2,…,Sn},每个集合Si都有一个特殊元素root[Si],称为集合代表.◆并查集支持三种操作：Init（X）:集合初始化：把元素xi加到集合Si中。每个集合Si只有一个独立的元素xi,并且元素xi就是集合Si的代表元素。Find(x):查找：查找xi所在集合Si的代表root[Si]。优化：路径压缩。Union(x,y):合并：把x和y所在的两个不同集合合并。并查集的森林结构实现采用森林结构实现并查集的基本思想是：

◆每个子集合用一棵树来表示。树中的结点用于存放集合中的元素。

◆树中的每个结点设置一个指向父亲的指针。

father[xi]

◆用根结点的元素代表该树所表示的集合。Init（X）:集合初始化：

father[xi]=0;每个结点的都是树根，代表元素。Find(x):查找：查找xi所在集合Si的代表root[Si]。即：查找xi所在树的树根结点（代表元素）。顺着x往上找，直到找到根节点，也就确定了x所在的集合。Union(x,y):合并x和y所在的不同集合。

p=find(x)；q=find(y);ifp<>qthenfather[p]=q三种操作：树根（集合代表元素）：

Father[1]=0;

father[8]=0;

father[11]=0孩子结点：

father[2]=1;

father[4]=3;

father[5]=4;

father[9]=8查找：

find(5)=1

find(7)=1

find(9)=8find(11)=11

find(1)=1

find(8)=8合并：union（x，y）

union（5，9）

p=find(5)=1;

q=find(9)=8;father[q]=p;或father[p]=q

father[8]=1;father[1]=8一、并查集的定义引例：【犯罪团伙】

警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。输入：第一行：n（<10000,罪犯数量），第二行：m（<100000，关系数量）以下若干行：每行两个数：I和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。输出：一个整数，犯罪团伙的数量。样例：输入：118124534135671051089输出：3测试数据说明：共10个测试数据：（1）5个数据：n<=1000,m<=5000;（2）5个数据：10000>n〉=9000,

100000>m〉=90000;算法一：图的dfs：proceduredfs(i:longint);varj:longint;beginvisited[i]:=1;forj:=1tondoif(a[i,j]=1)and(visited[j]=0)thendfs(j);end;主程序：Beginfori:=1tondoifvisited[i]=0thenbegindfs(i);inc(s);end;writeln(s);end.只能过前5个数据模型：无向图的连通子图的数量算法二：1）、开始把n个人看成n个独立集合。2）、每读入两个有联系的人i和j，查找i和j所在的集合f(i)和

f(j)，如果f(i)和f(j)是同一个集合，不作处理；如果f(i)

和f(j)属于不同的集合，则合并集合f(i)和f(j)为一个集合。（每个集合可以找一个代表元素）3）、最后统计集合的个数即可得到问题的解。二、并查集的树结构实现采用树结构实现并查集的基本思想是：每个集合用一棵树来表示。树的结点用于存储集合中的元素。树中的每个结点存放一个指向父亲的指针。在实际使用中往往用根结点的元素代表该树所表示的集合。图的连通子图的数量1）设：a[i]：为结点i的父亲指针。如果a[i]=0，则i是树的根，否则a[i]指向结点i的根。开始初始化时：a[i]=0，所有结点都是独立的点，看成独立的一棵树根。2）每读入两个结点x，y，找x的树根p，令a[x]=p;找y的树根q，令a[y]=q;如果x和y属于同一棵树即：p=q，不做处理；如果属于不同的两棵树即：p<>q，则合并两棵树，具体操作是：把p看作q的孩子或者把q看作p的孩子(a[p]=q或者a[q]=p)。3）最后统计树的数量，即a[i]=0的结点的数量。输入：118124534135671051089constmax=10000;vara:array[1..max]oflongint;i,j,m,n,sum,x,y,p,q:longint;functionfind(i:longint):longint;{非递归算法找i的根}varj,k,t:longint;beginj:=i;whilea[j]<>0doj:=a[j];find:=j;end;算法：beginassign(input,'group1.in');reset(input);readln(n);readln(m);fillchar(a,sizeof(a),0);{默认根标志是0，开始全是树根}fori:=1tomdobeginreadln(x,y);p:=find(x);{查找x的根}q:=find(y);{查找y的根}ifp<>qthena[q]:=p;{合并p和q子树}end;sum:=0;{树根记数}fori:=1tondoifa[i]=0theninc(sum);{记录树根结点}writeln(sum);close(input);end.查找find(i)的优化:路径压缩:

当找到i所在的树根j后，把i的父亲指针指向j，即a[i]=j。同时把i到根j路径上的所有结点k的父亲都指向j，即a[k]=j；把i到j这条路径的所有子结点都看作根j的儿子，或者说所有子结点的父亲指针都指向根j。这样可以减小以后的查找次数，这个优化称为路径压缩。实现路径压缩的简单算法：从结点到根走两遍：第一遍找根；第二遍是将路径上的所有结点的父亲都设为跟。路径压缩程序：非递归算法：functionfind(i:longint):longint;{非递归算法找i的根}varj,k,t:longint;beginj:=i;whilea[j]<>0doj:=a[j];find:=j;k:=i;{从i开始对子树结点进行路径压缩}whilea[k]<>0dobegint:=k;k:=a[k];a[t]:=j;end;end;functionfind(i:longint):longint;{采用递归算法：寻找结点i的树根，并对结点i所在的子树进行路径压缩，返回调整后的i的父指针（根）}begin

ifa[i]=0thenexit(i);{若i为根，返回本身结点序号}

ifa[a[i]]=0thenexit(a[i]);{若i的父结点为根，则返回父结点}

find:=find(a[i]);{递归找根结点}

a[i]:=find;{路径压缩：找到根后，按原路返回i的同时，进行中间结点的逆序路径压缩，一次性完成}end;递归算法（多采用此法）：合并的优化改进:1、按树的结点个数合并

2、按树的高度合并◆克鲁斯卡尔（kruskal）求最小生产树算法步骤：1、把图中的边按权值从小到大排序。2、按从小到大的顺序依次向树中加边。在添加每一条边（u，v）时，如果u和V两个点都已在树中，一旦添加，就回构成回路，所以放弃该边，在向后找下一条边。3、直到添加n-1条边。关键：加边时不能构成回路：边的两个顶点是否已在树中。1243517301024723512345

//边表存储边，从小到大排序ans:=0;fori:=1tomdobegin

x:=find(u[i]);y:=find(v[i]);ifx<>ythenbegin