第三弹数据结构进阶的主要内容有以下几部分:线段树、树状数组、并查集。

一、线段树

一:线段树基本概念

1:概述

线段树,类似区间树,是一个完全二叉树,它在各个节点保存一条线段(数组中的一段子数组),使用线段树可以快速的查找某一个节点在若干条线段中出现的次数主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(lgN)!线段树的作用一般都不是对线段进行处理,所以即使不包含某个区间,但是其端点还是存在的,所以我们只需要对它的端点进行处理就好了。

性质:父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b],线段树需要的空间为数组大小的四倍


2:基本操作

【以下以 求区间最大值为例】
先看声明:

#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <algorithm>  
#include <cmath>  
using namespace std;  
const int maxn=50000;  
struct node{  
    int l;  
    int r;  
    int sum;  
}tree[(maxn+5)*9];  
int a[maxn+5];


【创建线段树(初始化)】:

       由于线段树是用二叉树结构储存的,而且是近乎完全二叉树的,所以在这里我使用了数组来代替链表上图中区间上面的红色数字表示了结构体数组中对应的下标。

在完全二叉树中假如一个结点的序号(数组下标)为 I ,那么 (二叉树基本关系)

I 的父亲为 I/2,

I 的另一个兄弟为 I/2*2 或 I/2*2+1

I 的两个孩子为 I*2 (左)   I*2+1(右)

有了这样的关系之后,我们便能很方便的写出创建线段树的代码了。

void build(int l,int r,int index){  
    tree[index].l=l;  
    tree[index].r=r;  
    if(l==r){  
        tree[index].sum=a[l];  
        return;  
    }  
    int middle = (l+r)/2;  
    build(l, middle, 2*index);  
    build(middle+1, r, 2*index+1);  
    tree[index].sum=tree[2*index].sum+tree[2*index+1].sum;  
}  

【单点更新线段树】:

       由于我事先用 father[ ] 数组保存过 每单个结点 对应的下标了,因此我只需要知道第几个点,就能知道这个点在结构体中的位置(即下标)了,这样的话,根据之前已知的基本关系,就只需要直接一路更新上去即可。

void update(int number,int index,int ans)  //单点更新  
{   
    tree[index].sum += ans;  
    if(tree[index].l==tree[index].r&&tree[index].l==number){  
        return;  
    }  
    int middle = (tree[index].l+tree[index].r)/2;  
    if(middle>=number)//这个数在右边子树 
	{  
        update(number, 2*index, ans);  
    }
	else//这个数在左边子树 
	{  
        update(number, 2*index+1, ans);  
    }  
}  

【查询区间】: 
       将一段区间按照建立的线段树从上往下一直拆开,直到存在有完全重合的区间停止。对照图例建立的树,假如查询区间为 [1,6] 
                                                      

最下边的区间为完全重合的区间。

int getSum(int l,int r,int index)//index代表结点的编号,一般都是从1开始 
{  
    if(tree[index].l==l&&tree[index].r==r)
	{  //找到了这个区间 
        return tree[index].sum;  
    }  
    int middle = (tree[index].l+tree[index].r)/2;  
    if(middle<l)
	{  // 区间全在右半树 
        return getSum(l, r, 2*index+1);  
    }
	else if(middle>=r)
	{  //区间全在左半树 
        return getSum(l,r,2*index);  
    }
	else
	{  //区间左右树都有 
        return getSum(l, middle, 2*index)+getSum(middle+1, r, 2*index+1);  
    }  
}  
  

强烈推荐线段树博文--->夜深人静写算法


二、典型模板

线段树求和模板//只适用于区间都在左右同侧的情况。

<span style="font-size:14px;">#include<iostream>
#include<string.h>
#include<stdio.h>
#define lson id*2    //id的左子树编号
#define rson id*2+1    //id的右子树编号
using namespace std;
int ans;
//id是每个所在区间的编号
//l和r是id所代表区间的左右节点

int tre[2000700];
int a,b,c,d,n,m,k;
int push(int id)
{
    tre[id]=tre[lson]+tre[rson];//把子叶的值拿来更新父亲节点的值
    return 0;
}


int build(int id,int l,int r)   //树的初始化,必须的操作,虽然我也不知道为什么,好像是为了给每个点编号
{
    if (l>r)    return 0;//去除非法状态,以下每个子函数都要写
    if (l==r)
                {
                tre[id]=0;
                return 0;

                }
    int mid=(l+r)/2;
    build(lson,l,mid);//递归左右子树
    build(rson,mid+1,r);//注意是mid+1
    push(id);
}
int add(int id,int l,int r,int pos,int num)     //在编号为id的区间【l,r】中,在pos位置的值增加num,同时更新它的所有祖宗节点的值都加num
{
    if(l>r) return 0;//判断非法状态
    if (l==r && r==pos)     //如果到了最后一层,更新值,记得return掉
        {
        tre[id]+=num;
        return 0;
        }
    int mid=(l+r)/2;
    if (pos<=mid)//如果pos在当前区间中点的左边,则在左子树中递归,反之在右子树中递归
        {
            add(lson,l,mid,pos,num);
        }
    if (pos>=mid+1)
        {
        add(rson,mid+1,r,pos,num);
        }
    push(id);//下一层递归完成后对本层进行更新
}
int query(int id,int l,int r,int L,int R)
{
    if (l>r || L>R)    return 0; //非法状态
    if (l>=L && r<=R)
        {
        ans+=tre[id];
        return 0;//一定记得return,都则id会大的飞起
        }
    int mid=(l+r)/2;
    if (L<=mid)    //如果所查询区间和【l,r】的左半边有重合,则递归求左半边,右半边同理
        {
        query(lson,l,mid,L,R);
        }
    if (mid+1<=R)
        {
        query(rson,mid+1,r,L,R);
        }
    return 0;
}
int main()
{

/******************
使用方法
1,初始化: build(1,1,maxx) maxx是所开数组的长度或者题目要求的长度(第二个1端点可以被更改)
2,给节点加值 add(1,1,maxx,pos,num)  pos是位置,num是数值</span><span style="font-family: Arial;"><span style="font-size:12px;">(第二个1是区间端点可以被更改)</span></span><span style="font-size:14px;">
3,查询区间[L,R]的和   query(1,1,maxx,L,R)</span><span style="font-family: Arial;">(第二个1是区间端点可以被更改)</span><span style="font-size:14px;">
******************/
build(1,1,1000);
int n,m,a,b;

cin>>n>>m;
for (int i=1;i<=n;i++)
        {
        scanf("%d%d",&a,&b);
        add(1,1,m,a,b);
        }
for (int i=1;i<=m;i++)
        {
        scanf("%d%d",&a,&b);
        ans=0;
        query(1,1,m,a,b);
        cout<<ans<<endl;
        }
}</span>

单点查询、区间查询最大值模板

<span style="font-family:microsoft yahei;font-size:18px;color:#555555;">/* 
线段树模板,先自学线段树原理
这里单点修改,区间查询最大值的代码
最小值只需要把max改成min即可
注意ans初始化
*/ 
#include<iostream>
#include<string.h>
#include<stdio.h>
#define lson id*2  //左儿子
#define rson id*2+1    //右儿子
using namespace std;
int tre[2000000];  //线段树
int ans=-19943;
int a,b,c,d,n,m;
int pushup(int id)   //儿子节点的信息传递到父亲节点
             //根据需要调节代码,下同
{
    tre[id]=max(tre[lson],tre[rson]);
    return 0;
}
int build(int id,int l,int r) //初始化
{
    if (l>r) return 0;
    if (l==r)
        {
        tre[id]=1;
        return 0;
        }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);//递归构造左右子树
    pushup(id);
    return 0;
}
int add(int id,int l,int r,int pos,int num)    //id是当前节点的编号,l&&r是id所代表区间的左右边界,pos是要增值的那个点(就比如要对区间[1,7]里的5所在位置增值,那么这个pos就是5),num是要增加的数值 
{ 
    if (l>r) return 0;//线段树中容易发生这种错误,因为每次mid+1可能大于r
    if (l==r && r==pos)    //如果l==r说明递归到了最底层,直接更新节点数值
        {
        tre[id]=num;
        return 0;
        }
    int mid=(l+r)/2;
    if (pos<=mid)    //如果要增值的点在mid左边,递归左边
        add(lson,l,mid,pos,num);
    if (pos>=mid+1)        //反之递归右边,注意这里是mid+1
        add(rson,mid+1,r,pos,num);
    pushup(id);    //更新当前节点的值
    return 0;
}
int query(int id,int l,int r,int L,int R)    //在编号为id的区间【l,r】中查找【L,R】区间的最大值
{
    if (l>r || L>R)  return 0;//判断非法状态
    if (L>r || R<l) return 0;
    if (l>=L && r<=R)
        {
        ans=max(ans,tre[id]);
                return 0;
                }
    int mid=(l+r)/2;
    if (mid>=L) //如果id区间的mid值包含在【L,R】之间,要递归查询id的左子树
        query(lson,l,mid,L,R);
    if (mid+1<=R)
        query(rson,mid+1,r,L,R);
    return 0;
}
int main()
{
	/******************
	使用方法
	1,初始化: build(1,1,maxx) maxx是所开数组的长度或者题目要求的长度(第二个1端点可以被更改)
	2,给节点加值 add(1,1,maxx,pos,num)  pos是位置,num是数值(第二个1是区间端点可以被更改)
	3,查询区间[L,R]的和  query(1,1,maxx,L,R)(第二个1是区间端点可以被更改)
	******************/	
	
        build(1,3,40);
        //第一个数是当前树的根节点的编号,第二三个数是区间左右边界 
        add(1,3,40,20,40);
        //第一个数是当前节点的编号,第二三数是第一个数所代表区间的左右边界,第四个数是要插入的节点编号,第五个数是要插入的数
        query(1,3,40,5,40);
        //在根节点的编号为第一个数的区间【第二个数,第三个数】中查找【第四个数,第五个数】区间的最大值
        cout<<ans<<endl;
}</span>


二、树状数组

一、树状数组是干什么的?

       平常我们会遇到一些对数组进行维护查询的操作,比较常见的如,修改某点的值、求1-x的区间的和,而这两种恰恰是树状数组的强项!当然,数据规模不大的时候,对于修改某点的值是非常容易的,复杂度是O(1),但是对于求一个区间的和就要扫一遍了,复杂度是O(N),如果实时的对数组进行M次修改或求和,最坏的情况下复杂度是O(M*N),当规模增大后这是划不来的!而树状数组干同样的事复杂度却是O(M*lgN),别小看这个lg,很大的数一lg就很小了,这个学过数学的都知道吧,不需要我说了。申明一下,看下面的文章一定不要急,只需要看懂每一步最后自然就懂了。

二、树状数组怎么干的?

        先看两幅图(网上找的,如果雷同,不要大惊小怪~),下面的说明都是基于这两幅图的,左边的叫A图吧,右边的叫B图:

      是不是很像一颗树?对,这就是为什么叫树状数组了~先看A图,a数组就是我们要维护和查询的数组,但是其实我们整个过程中根本用不到a数组,你可以把它当作一个摆设!c数组才是我们全程关心和操纵的重心。先由图来看看c数组的规则,其中c8 = c4+c6+c7+a8,c6 = c5+a6……先不必纠结怎么做到的,我们只要知道c数组的大致规则即可,很容易知道c8表示a1~a8的和,但是c6却是表示a5~a6的和,为什么会产生这样的区别的呢?或者说发明她的人为什么这样区别对待呢?答案是,这样会使操作更简单!看到这相信有些人就有些感觉了,为什么复杂度被lg了呢?可以看到,c8可以看作a1~a8的左半边和+右半边和,而其中左半边和是确定的c4,右半边其实也是同样的规则把a5~a8一分为二……继续下去都是一分为二直到不能分,可以看看B图。怎么样?是不是有点二分的味道了?对,说白了树状数组就是巧妙的利用了二分,她并不神秘,关键是她的巧妙!

       她又是怎样做到不断的一分为二呢?说这个之前我先说个叫lowbit的东西,lowbit(k)就是把k的二进制的高位1全部清空,只留下最低位的1,比如10的二进制是1010,则lowbit(k)=lowbit(1010)=0010(2进制),介于这个lowbit在下面会经常用到,这里给一个非常方便的实现方式,比较普遍的方法lowbit(k)=k&-k,这是位运算,我们知道一个数加一个负号是把这个数的二进制取反+1,如-10的二进制就是-1010=0101+1=0110,然后用1010&0110,答案就是0010了!明白了求解lowbit的方法就可以了,继续下面。介于下面讨论十进制已经没有意义(这个世界本来就是二进制的,人非要主观的构建一个十进制),下面所有的数没有特别说明都当作二进制。

       上面那么多文字说lowbit,还没说它的用处呢,它就是为了联系a数组和c数组的!ck表示从ak开始往左连续求lowbit(k)个数的和,比如c[0110]=a[0110]+a[0101],就是从110开始计算了0010个数的和,因为lowbit(0110)=0010,可以看到其实只有低位的1起作用,因为很显然可以写出c[0010]=a[0010]+a[0001],这就为什么我们任何数都只关心它的lowbit,因为高位不起作用(基于我们的二分规则它必须如此!),除非除了高位其余位都是0,这时本身就是lowbit。

既然关系建立好了,看看如何实现a某一个位置数据跟改的,她不会直接改的(开始就说了,a根本不存在),她每次改其实都要维护c数组应有的性质,因为后面求和要用到。而维护也很简单,比如更改了a[0011],我们接着要修改c[0011],c[0100],c[1000],这是很容易从图上看出来的,但是你可能会问,他们之间有申明必然联系吗?每次求解总不能总要拿图来看吧?其实从0011——>0100——>1000的变化都是进行“去尾”操作,又是自己造的词--'',我来解释下,就是把尾部应该去掉的1都去掉转而换到更高位的1,记住每次变换都要有一个高位的1产生,所以0100是不能变换到0101的,因为没有新的高位1产生,这个变换过程恰好是可以借助我们的lowbit进行的,k +=lowbit(k)

       好吧,现在更新的次序都有了,可能又会产生新的疑问了:为什么它非要是这种关系啊?这就要追究到之前我们说c8可以看作a1~a8的左半边和+右半边和……的内容了,为什么c[0011]会影响到c[0100]而不会影响到c[0101],这就是之前说的c[0100]的求解实际上是这样分段的区间 c[0001]~c[0010] 和区间c[0011]~c[0100]的和,数字太小可能不太理解,在比如c[0100]会影响c[1000],为什么呢?因为c[1000]可以看作0001~0100的和加上0101~1000的和,但是0101位置的数变化并不会直接作用于c[1000],因为它的尾部1不能一下在跳两级在产生两次高位1,是通过c[0110]间接影响的,但是,c[0100]却可以跳一级产生一次高位1。

       再换个思路讲一遍....

       从图中不难发现,c[k]存储的实际上是从k开始向前数k的二进制表示中右边第一个1所代表的数字个元素的和(这么说可能有点拗口,令lowbit为k的二进制表示中右边第一个1所代表的数字,然后c[k]里存的就是从a[k]开始向前数lowbit个元素之和)这么存有什么好处呢?无论是树状数组还是线段树,都用到了分块的思想,而树状数组采用这样的存储结构我想最主要的还是这样方便计算,我们可以用位运算轻松地算出lowbit.分析一下这样做的复杂度:对于更改元素来说,如果第i个元素被修改了,因为我们最终还是要求和,所以可以直接在c数组里面进行相应的更改,如图中的例子,假设更改的元素是a[2],那么它影响到得c数组中的元素只有c[2],c[4],c[8],我们只需一层一层往上修改就可以了,这个过程的最坏的复杂度也不过O(logN);对于查找来说,如查找s[k],只需查找k的二进制表示中1的个数次就能得到最终结果,比如查找s[7],7的二进制表示中有3个1,也就是要查找3次,到底是不是呢,我们来看上图,s[7]=c[7]+c[6]+c[4],可能你还不知道怎么实现这个过程.
还以7为例,二进制为0111,右边第一个1出现在第0位上,也就是说要从a[7]开始向前数1个元素(只有a[7]),即c[7];
然后将这个1舍掉,得到6,二进制表示为0110,右边第一个1出现在第1位上,也就是说要从a[6]开始向前数2个元素(a[6],a[5]),即c[6];
然后舍掉用过的1,得到4,二进制表示为0100,右边第一个1出现在第2位上,也就是说要从a[4]开始向前数4个元素(a[4],a[3],a[2],a[1]),即c[4].

         可能上面说的你比较绕了,那么此时你只需注意:c的构成性质(其实是分组性质)决定了c[0011]只会直接影响c[0100],而c[0100]只会直接影响[1000],而下表之间的关系恰好是也必须是k +=lowbit(k)。此时我们就是写出跟新维护树的代码:

int lowbit(int x)
{
    return x & (-x);
}

void add(int k,int num)  
{  
    while(k<=MAX)  //n是树状数组的大小
    {  
        tree[k]+=num;  
        k+=lowbit(k);  
    }  
} 

有了上面的基础,说求和就比较简单了。比如求0001~0110的和就直接c[0100]+c[0110],分析方法与上面的恰好逆过来,而且写法也是逆过来的,具体就不累述了。如果是要求i-j区间的和,那么只需要用1-j的和减去1-(i-1)的和。

int read(int k)//1~k的区间和  
{  
    int sum=0;  
    while(k)  
    {  
        sum+=tree[k];  
        k-=lowbit(k);  
    }  
    return sum;  
} 
//二维add、sum
void modify(int x,int y,int data)
{
    for(int i=x;i<MAXN;i+=lowbit(i))
        for(int j=y;j<MAXN;j+=lowbit(j))
            a[i][j]+=data;
}
int get_sum(int x,int y)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            res+=a[i][j];
    return res;
}
树状数组的应用是, 树状数组一开始都是空的 ,然后对这个数组里面的元素不断进行add或者sum等修改操作,从而完成题目要求。


三、并查集

并查集顾名思义就是有“合并集合”和“查找集合”两种操作的关于数据结构的一种算法。并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等。使用并查集时,首先会存在一组不相交的动态集合 S={S1,S2,⋯,Sk},一般都会使用一个整数表示集合中的一个元素。每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的,具体选择哪个元素作为代表一般也是不关心的。我们关心的是,对于给定的元素,可以很快的找到这个元素所在的集合(的代表),以及合并两个元素所在的集合,而且这些操作的时间复杂度都是常数级的。

并查集的基本操作有三个:

  1. makeSet(s):建立一个新的并查集,其中包含 s 个单元素集合。
  2. unionSet(x, y):把元素 x 和元素 y 所在的集合合并,要求 x 和 y 所在的集合不相交,如果相交则不合并。
  3. find(x):找到元素 x 所在的集合的代表,该操作也可以用于判断两个元素是否位于同一个集合,只要将它们各自的代表比较一下就可以了。

并查集的实现原理也比较简单,就是使用树来表示集合,树的每个节点就表示集合中的一个元素,树根对应的元素就是该集合的代表,如图 1 所示。

                                                                                                  图 1 并查集的树表示

图中有两棵树,分别对应两个集合,其中第一个集合为  {a,b,c,d},代表元素是a;第二个集合为 {e,f,g},代表元素是e.

树的节点表示集合中的元素,指针表示指向父节点的指针,根节点的指针指向自己,表示其没有父节点。沿着每个节点的父节点不断向上查找,最终就可以找到该树的根节点,即该集合的代表元素。

现在,应该可以很容易的写出 makeSet 和 find 的代码了,假设使用一个足够长的数组来存储树节点(很类似之前讲到的静态链表),那么 makeSet 要做的就是构造出如图 2 的森林,其中每个元素都是一个单元素集合,即父节点是其自身:

                                                                                                   图 2 构造并查集初始化

相应的代码如下所示,时间复杂度是 O(n)

const int MAX = 500;
int father[MAX];  //father[x]表示x的父节点
int sign[MAX];    //sign[x] 用来记录查找根节点时,途中所路过的节点,压缩路径的时候用到

int rank[MAX]     //rank[x]  表示x节点所在树的深度

 
void makeSet(int size) {
    for(int i = 0;i < size;i++) 
    {
       father[i] = i;
       rank[i]=0;
    }
}


接下来,就是 find 操作了,如果每次都沿着父节点向上查找,那时间复杂度就是树的高度,完全不可能达到常数级。这里需要应用一种非常简单而有效的策略——路径压缩。

路径压缩,就是在每次查找时,令查找路径上的每个节点都直接指向根节点,如图 3 所示。

                                                                                                             图 3 路径压缩

find的递归实现:

int find(int x) {
    
if(father[x] != x)

         {

                  father[x] = find(father[x]); //这是一个递归的过程,回溯时压缩路径

         }

         return father[x];

}


最后是合并操作 unionSet,并查集的合并也非常简单,就是将一个集合的树根指向另一个集合的树根,如图 4 所示。

                                                                                                        图 4 并查集的合并

这里也可以应用一个简单的启发式策略——按秩合并。该方法使用秩来表示树高度的上界,在合并时,总是将具有较小秩的树根指向具有较大秩的树根。简单的说,就是总是将比较矮的树作为子树,添加到较高的树中。为了保存秩,需要额外使用一个与 uset 同长度的数组,并将所有元素都初始化为 0。

void unionSet(int x, int y) {
   
         x = find(x);

         y = find(y);

         if(x == y)  return ;    //若为同一集合,则直接返回

         if(rank[x] > rank[y])   //如果x树的深度比y树深,y树接到x树

         {

                  father[y] = x;

         }

         else if(rank[x] < rank[y])

         {

                  father[x] = y;

         }

         else if(rank[x] ==rank[y])  //若两树的深度一样

         {

                  father[x] = y;           //则x树接到y树

                  rank[y]++;              //此时y树的深度+1

         }

    }
}

除了按秩合并,并查集还有一种常见的策略,就是按集合中包含的元素个数(或者说树中的节点数)合并,将包含节点较少的树根,指向包含节点较多的树根。这个策略与按秩合并的策略类似,同样可以提升并查集的运行速度,而且省去了额外的 rank 数组。

这样的并查集具有一个略微不同的定义,即若 uset 的值是正数,则表示该元素的父节点(的索引);若是负数,则表示该元素是所在集合的代表(即树根),而且值的相反数即为集合中的元素个数。相应的代码如下所示,同样包含递归和非递归的 find 操作:

const  int  MAXSIZE = 500;
int  uset[MAXSIZE];
 
void  makeSet( int  size) {
     for ( int  i = 0;i < size;i++) uset[i] = -1;
}
int  find( int  x) {
     if  (uset[x] < 0)  return  x;
     uset[x] = find(uset[x]);
     return  uset[x];
}
int  find( int  x) {
     int  p = x, t;
     while  (uset[p] >= 0) p = uset[p];
     while  (x != p) {
         t = uset[x];
         uset[x] = p;
         x = t;
     }
     return  x;
}
void  unionSet( int  x,  int  y) {
     if  ((x = find(x)) == (y = find(y)))  return ;
     if  (uset[x] < uset[y]) {
         uset[x] += uset[y];
         uset[y] = x;
     else  {
         uset[y] += uset[x];
         uset[x] = y;
     }
}

如果要获取某个元素 x 所在集合包含的元素个数,可以使用 -uset[find(x)] 得到。


为了解释并查集的原理,我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?

我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。


下面我们来看并查集的实现。 int pre[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。 find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。

int find(int x)                                                                  //查找我(x)的掌门

{

    int r=x;                                                                       //委托 r 去找掌门

    while (pre[r ]!=r)                                                        //如果r的上级不是r自己(也就是说找到的大侠他不是掌门 = =)

    r=pre[r ] ;                                                                   // r 就接着找他的上级,直到找到掌门为止。

    return  r ;                                                                   //掌门驾到~~~

}

再来看看join函数,就是在两个点之间连一条线,这样一来,原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办,画条线就行了。但我们现在是用并查集来描述武林中的状况的,一共只有一个pre[]数组,该如何实现呢? 还是举江湖的例子,假设现在武林中的形势如图所示。虚竹小和尚与周芷若MM是我非常喜欢的两个人物,他们的终极boss分别是玄慈方丈和灭绝师太,那明显就是两个阵营了。我不希望他们互相打架,就对他俩说:“你们两位拉拉勾,做好朋友吧。”他们看在我的面子上,同意了。这一同意可非同小可,整个少林和峨眉派的人就不能打架了。这么重大的变化,可如何实现呀,要改动多少地方?其实非常简单,我对玄慈方丈说:“大师,麻烦你把你的上级改为灭绝师太吧。这样一来,两派原先的所有人员的终极boss都是师太,那还打个球啊!反正我们关心的只是连通性,门派内部的结构不要紧的。”玄慈一听肯定火大了:“我靠,凭什么是我变成她手下呀,怎么不反过来?我抗议!”抗议无效,上天安排的,最大。反正谁加入谁效果是一样的,我就随手指定了一个。这段函数的意思很明白了吧?

void join(int x,int y)                                                                   //我想让虚竹和周芷若做朋友

{

    int fx=find(x),fy=find(y);                                                       //虚竹的老大是玄慈,芷若MM的老大是灭绝

    if(fx!=fy)                                                                               //玄慈和灭绝显然不是同一个人

    pre[fx ]=fy;                                                                           //方丈只好委委屈屈地当了师太的手下啦

}

再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么胎唇样,我也完全无法预计,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。 设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能揍。 于是赶紧打电话问自己的上级:“你是不是掌门?” 上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。” 一路问下去,原来两人的最终boss都是东厂曹公公。 “哎呀呀,原来是记己人,西礼西礼,在下三营六组白面葫芦娃!” “幸会幸会,在下九营十八组仙子狗尾巴花!” 两人高高兴兴地手拉手喝酒去了。 “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩。 “哦,对了,还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧,省得级别太低,以后查找掌门麻环。” “唔,有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码,看得懂很好,看不懂也没关系,直接抄上用就行了。总之它所实现的功能就是这么个意思。