数据基础教程12

7.9.1树算法设计7.9*树算法设计和并查集树分为有根树和无根树。有根树中有且仅有一个根结点并且默认树中边（分支）是有向边，也称为有向树。无根树实际上是一个连通无环图，没有根结点，树中的边是无向边。本章中的树默认为有根树，无根树看成无向图，在下一章讨论。1/421.双亲存储结构2.孩子链存储结构3.孩子兄弟链存储结构根据问题需要选择合适的存储结构2/42【例7.24】POJ1330—求树中两个结点的最近公共祖先（LCA）。

问题描述：有根树是计算机科学和工程中众所周知的数据结构，下图是一棵有根树。在该图中，每个结点标有1～16的整数。结点8是树的根。如果结点x位于根结点到结点y之间的路径中，则结点x是结点y的祖先。注意这里规定一个结点也是自己的祖先，如结点7的祖先有结点8，4，6和7。

如果结点x是结点y和结点z的祖先，则结点x称为两个不同结点y和z的公共祖先，因此结点8和4是结点16和7的公共祖先。如果x是y和z的共同祖先并且在所有共同祖先中最接近y和z，则结点x被称为结点y和z的最近公共祖先。因此，结点16和7的最近公共祖先是结点4，因为结点4比结点8更靠近结点16和7。编写一个程序，找到树中两个不同结点的最近公共祖先。859647101151116231214133/42

输入格式：输入由T个测试用例组成。测试用例个数（T）在输入文件的第一行中给出。每个测试用例以整数N的行开始，整数N是树中的结点数，2≤N≤10,000。结点用整数1～N标记。接下来的N-1行中的每一行包含一对表示边的整数，第一个整数是第二个整数的父结点。请注意，具有N个结点的树具有恰好N-1个边。每个测试用例的最后一行包含两个不同的整数，需要计算它们的最近公共祖先。

输出格式：为每个测试用例输出一行，该行应包含最近公共祖先结点的编号。4/42输入样例：2 //表示有2个测试用例16 //测试用例1的数据114851016594684410113615101167102163811612167 //求结点16和7的LCA5 //测试用例2的数据2334311535 //求结点3和5的LCA输出样例：435/42

这里的树是有根树，首先由输入创建树存储结构，再对于给定的x和y结点，求LCA的过程如下：

（1）求出x结点的层次lx，y结点的层次ly。

（2）若lx≠ly，将较高层次的结点上移直到它们处于相同层次。

（3）若x≠y，再将它们同步上移直到x=y。这样的x或者y结点就是LCA。

从上述过程看出，主要涉及结点上移操作，为此树采用双亲存储结构较合适。由于结点是通过编号唯一标识的，并且N个结点的编号是1～N，所以直接采用int类型的parent数组作为双亲存储结构，parent[i]表示结点i的双亲结点编号。

那么如何确定根结点呢？任何一个结点i有双亲，则parent[i]一定是1～N的整数，为此将parent数组所有元素初始化为-1，如果一个结点i的双亲father[i]为-1，则结点i就是根结点。6/428596471011511162312141385964710115111623121413-1结点16和7的LCA是结点4！7/42importjava.util.*;importjava.util.Scanner;publicclassMain{finalstaticintMAXN=10005;

staticint[]parent=newint[MAXN];//树的双亲存储结构publicstaticintLevel(intx){ //求x结点的层次intcnt=0;while(x!=-1){ //找到根为止x=parent[x]; //结点x上移cnt++; //累计上移的次数就是原x结点的层次}returncnt;}8/42publicstaticintsolve(intx,inty){//求x和y结点的最近公共祖先结点

intlx=Level(x); //求x结点的层次lxintly=Level(y); //求y结点的层次lywhile(lx>ly){ //将较高层次的x结点上移x=parent[x];lx--;}while(ly>lx){ //将较高层次的y结点上移y=parent[y];ly--;}while(x!=y){ //当x和y移到相同层次，再找LCAx=parent[x];y=parent[y];}returnx;}9/42publicstaticvoidmain(String[]args){Scannerfin=newScanner(System.in);intT,N,a,b,x,y;T=fin.nextInt();while(T-->0){N=fin.nextInt();for(inti=0;i<=N;i++) //初始化N个结点的双亲为-1parent[i]=-1;for(inti=1;i<N;i++){ //输入N-1条边,创建双亲存储结构a=fin.nextInt(); //输入一条边b=fin.nextInt();parent[b]=a;}x=fin.nextInt(); //输入查询y=fin.nextInt();intans=solve(x,y); //求LCASystem.out.println(ans); //输出结果} }}10/427.9.2并查集1.并查集的定义给定n个结点的集合，结点编号为1～n，再给定一个等价关系，由等价关系产生所有结点的一个划分，每个结点属于一个等价类，所有等价类是不相交的。需要求一个结点所属的等价类，以及合并两个等价类。（1）Init()：初始化。（2）Find(intx)：查找x结点所属的等价类。（3）Union(intx，inty)：将x和y所属的两个等价类合并。求解该问题的基本运算上述数据结构称为并查集11/422.并查集的实现并查集就是一个森林。每个等价类用一棵树表示，包含该等价类的所有结点，即结点子集。每个子集通过一个代表来识别，代表即该子集中的某个结点，通常选择根做这个代表。Axy12/42

问题描述：如果已经得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系就十分复杂。在这种情况下，就需要应用并查集。

为了将问题简化，将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，可以推出Marry和Ben是亲戚。经典示例13/42

输入：第一部分以N，M开始。N为问题涉及的人的个数（1≤N≤20000）。这些人的编号为1，2，3，…，

N。

下面有M行（1≤M≤1000000），每行有两个数ai、bi，表示已知ai和bi是亲戚。

第二部分以Q开始。以下Q行有Q个询问（1≤Q≤1000000），每行为ci和di，表示询问ci和di是否为亲戚。

输出：对于每个询问ci、di，输出一行：若ci和di为亲戚，则输出"Yes"，否则输出"No"。解决分类问题14/42输入样例：107 //N=10，M=7245713891256233 //Q=33471089类似于离散数学中的等价类问题：给定一个集合U和一个等价关系R，产生具有等价关系的等价类。15/42采用集合的思路求解输入关系分离集合初始状态{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}，{9}，{10}（2，4）{1}，{2，4}，{3}，{5}，{6}，{7}，{8}，{9}，{10}（5，7）{1}，{2，4}，{3}，{5，7}，{6}，{8}，{9}，{10}（1，3）{1，3}，{2，4}，{5，7}，{6}，{8}，{9}，{10}（8，9）{1，3}，{2，4}，{5，7}，{6}，{8，9}，{10}（1，2）{1，2，3，4}，{5，7}，{6}，{8，9}，{10}（5，6）{1，2，3，4}，{5，6，7}，{8，9}，{10}（2，3）{1，2，3，4}，{5，6，7}，{8，9}，{10}16/42{1，2，3，4}，{5，6，7}，{8，9}，{10}343、4在同一个集合中Yes求解：7107、10不在同一个集合中No898、9在同一个集合中Yes结果集合：17/42并查集的数据结构记录了一组分离的动态集合S={S1，S2，…，Sk}。

每个动态集合Si（1≤i≤k）通过一个“代表”加以标识，该代表即为所代表的集合中的某个元素。对于集合Si，选取其中哪个元素作为代表是任意的。{{1，2，3，4}，{5，6，7}，{8，9}，{10}}18/42对于给定的编号为1～n的n个元素，x表示其中的一个元素，设并查集为S，并查集的实现需要支持如下运算：Init(S，n)：初始化并查集S，即S={S1，S2，…，Sn}，每个动态集合Si（1≤i≤n）仅仅包含一个编号为i的元素，该元素作为集合Si的“代表”。FIND(S，x)：返回并查集S中x元素所在集合的代表。UNION(S，x，y)：在并查集S中将x和y两个元素所在的动态集合（例如Sx和Sy）合并为一个新的集合Sx∪Sy。{{1，2，3，4}，{5，6，7}，{8，9}，{10}}19/42

用有根树来表示集合，树中的每个结点包含集合的一个成员，每棵树表示一个集合。多个集合形成一个森林，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点都用一个父指针表示它的附属关系。{1，2，3，4}集合432120/42

在并查集中，每个分离集合对应的一棵树，称为分离集合树。整个并查集也就是一棵分离集合森林。

4个集合{1，2，3，4}、{5，6，7}、{8，9}、{10}，分别以4、7、9和10表示对应集合的编号。4321{1，2，3，4}集合756{5，6，7}集合98{8，9}集合10{10}集合21/42几个问题查找x4321{1，2，3，4}集合用数组存放：t[x]对应x结点1?22/42查找x所在的子集4321{1，2，3，4}集合查找1所在的子集合：3次比较查找1所在的子集合：4次比较4321{1，2，3，4}集合子树高度越小越好223/42初始状态{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}，{9}，{10}12345678910（2，4）{1}，{2，4}，{3}，{5}，{6}，{7}，{8}，{9}，{10}12345678910合并过程parent324/42（5，7）{1}，{2，4}，{3}，{5，7}，{6}，{8}，{9}，{10}123456789101234567891025/42（1，3）{1，3}，{2，4}，{5，7}，{6}，{8}，{9}，{10}123456789101234567891026/42（8，9）{1，3}，{2，4}，{5，7}，{6}，{8，9}，{10}123456789101234567891027/421234（1，2）{1，2，3，4}，{5，7}，{6}，{8，9}，{10}5678910123412345678910改为28/42在一棵高度较低的树中查找根结点的编号（即该集合的代表）所花的时间较少，如何保证构造的分离集合树较低呢？两棵分离集合树A和B，高度分别为hA和hB，若hA>hB，应将B树作为A树的子树；否则，将A树作为B树的子树。总之，总是高度较小的分离集合树作为子树。29/42查找中的路径压缩430/42ABxABxCCfinalstaticintMAXN=1005; //最多结点个数staticint[]parent=newint[MAXN]; //并查集存储结构staticint[]rank=newint[MAXN]; //存储结点的秩staticintn; //实际结点个数并查集的基本存储结构（实际上是森林的双亲存储结构）如下：31/42voidInit(){ //初始化运算for(inti=1;i<=n;i++){parent[i]=i;rank[i]=0;}}并查集的基本运算算法时间复杂度为O(n)。32/42intFind(intx){ //查找x结点的根结点

if(x!=parent[x])parent[x]=Find(parent[x]); //路径压缩returnparent[x];}时间复杂度为O(log2n)，接近O(1)。ABxABxCC33/42intFind(intx){ //查找x结点的根结点

if(x!=parent[x])parent[x]=Find(parent[x]); //路径压缩returnparent[x];}用迭代方式实现intFind(intx){ //查找x结点的根结点

intrx=x;while(rx!=parent[rx])rx=parent[rx]; //找到x路径压缩inty=x;

while(y!=rx){ //路径压缩inttmp=parent[y];parent[y]=rx;y=tmp;}returnrx;}34/42voidUnion(intx,inty){ //x和y的两个集合的合并intrx=Find(x); //在查找中包含路径压缩intry=Find(y);if(rx==ry) //x和y属于同一棵树的情况

return;if(rank[rx]<rank[ry])

parent[rx]=ry;

//rx结点作为ry的孩子else{if(rank[rx]==rank[ry]) //秩相同，合并后rx的秩增1rank[rx]++;

parent[ry]=rx;

//ry结点作为rx的孩子}}时间复杂度为O(log2n),接近O(1)。xrxyryrank[rx]<rank[ry]xrxyry35/42【例7.25】HDU1232—畅通工程问题。

问题描述：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N（N<1000）和道路数目M，随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。注意两个城市之间可以有多条道路相通，也就是说：33121221这种输入也是合法的。当N为0时，输入结束，该用例不被处理。36/42输出格式：对每个测试用例，在一行里输出最少还需要建设的道路数目。输入样例：4213433312132352123599900输出样例：10299837/42要使全省任何两个城镇间都实现交通，最少的道路是所有城镇之间都有一条路径，即全部城镇构成一棵树。采用并查集求解，由输入构造并查集，每棵子树中的所有城镇是有路径的，求出其中子树的个数ans，那么最少还需要建设的道路数就是ans-1。Ans=3

需要建设的道路数=238/42importjava.util.*;importjava.util.Scanner;publicclassMain{finalstaticintMAXN=1005;staticint[]parent=newint[MAXN]; //并查集存储结构staticint[]rank=newint[MAXN]; //存储结点的秩staticintn; //n个城镇

staticintm; //m条道路publicstaticvoidInit() { //并查集初始化

for(inti=1;i<=n;i++){parent[i]=i;rank[i]=0;}}publicstaticintFind(intx){ //并查集中查找x结点的根结点

if(x!=parent[x])pare