为了解释并查集的原理, 我将举一个有趣的例子.
话说江湖上散落着各式各样的大侠, 有上千个之多. 他们没有什么正当职业, 整天背着剑在外面走来走去, 碰到和自己不是一路人的, 就免不了要打一架. 但大侠们有一个优点就是讲义气, 绝对不打自己的朋友. 而且他们信奉 "朋友的朋友就是我的朋友", 只要是能通过朋友关系串联起来的, 不管拐了多少个弯, 都认为是自己人. 这样一来, 江湖上就形成了一个一个的帮派, 通过两两之间的朋友关系串联起来. 而不在同一个帮派的人, 无论如何都无法通过朋友关系连起来, 于是就可以放心往死了打. 但是两个原本互不相识的人, 如何判断是否属于一个朋友圈呢?
我们可以在每个朋友圈内推举出一个比较有名望的人, 作为该圈子的代表人物. 这样, 每个圈子就可以这样命名 "中国同胞队" 美国同胞队 "...... 两人只要互相对一下自己的队长是不是同一个人, 就可以确定敌友关系了.
但是还有问题啊, 大侠们只知道自己直接的朋友是谁, 很多人压根就不认识队长要判断自己的队长是谁, 只能漫无目的的通过朋友的朋友关系问下去:"你是不是队长? 你是不是队长?" 这样, 想打一架得先问个几十年, 饿都饿死了, 受不了. 这样一来, 队长面子上也挂不住了, 不仅效率太低, 还有可能陷入无限循环中. 于是队长下令, 重新组队. 队内所有人实行分等级制度, 形成树状结构, 我队长就是根节点, 下面分别是二级队员, 三级队员. 每个人只要记住自己的上级是谁就行了. 遇到判断敌友的时候, 只要一层层向上问, 直到最高层, 就可以在短时间内确定队长是谁了. 由于我们关心的只是两个人之间是否是一个帮派的, 至于他们是如何通过朋友关系相关联的, 以及每个圈子内部的结构是怎样的, 甚至队长是谁, 都不重要了. 所以我们可以放任队长随意重新组队, 只要不搞错敌友关系就好了. 于是, 门派产生了.
下面我们来看并查集的实现. int pre[1000]; 这个数组, 记录了每个大侠的上级是谁. 大侠们从 1 或者 0 开始编号 (依据题意而定),pre[15]=3 就表示 15 号大侠的上级是 3 号大侠. 如果一个人的上级就是他自己, 那说明他就是掌门人了, 查找到此为止. 也有孤家寡人自成一派的, 比如欧阳锋, 那么他的上级就是他自己. 每个人都只认自己的上级. 比如胡青牛同学只知道自己的上级是杨左使. 张无忌是谁? 不认识! 要想知道自己的掌门是谁, 只能一级级查上去.
findr 这个函数就是找掌门用的, 意义再清楚不过了
- int findr(int root) // 查找掌门
- {
- int son, tmp;
- son = root;
- while(root != pre[root]) // 我的上级不是掌门
- root = pre[root];
- while(son != root) // 我就找他的上级, 直到掌门出现
- {
- tmp = pre[son];
- pre[son] = root;
- son = tmp;
- }
- return root; // 掌门驾到~~
- }
再来看看 unite 函数, 就是在两个点之间连一条线, 这样一来, 原先它们所在的两个板块的所有点就都可以互通了. 这在图上很好办, 画条线就行了. 但我们现在是用并查集来描述武林中的状况的, 一共只有一个 pre[] 数组, 该如何实现呢? 还是举江湖的例子, 假设现在武林中的形势如图所示. 虚竹帅锅与周芷若 MM 是我非常喜欢的两个人物, 他们的终极 boss 分别是玄慈方丈和灭绝师太, 那明显就是两个阵营了. 我不希望他们互相打架, 就对他俩说:"你们两位拉拉勾, 做好朋友吧." 他们看在我的面子上, 同意了. 这一同意可非同小可, 整个少林和峨眉派的人就不能打架了. 这么重大的变化, 可如何实现呀, 要改动多少地方? 其实非常简单, 我对玄慈方丈说:"大师, 麻烦你把你的上级改为灭绝师太吧. 这样一来, 两派原先的所有人员的终极 boss 都是师太, 那还打个球啊! 反正我们关心的只是连通性, 门派内部的结构不要紧的." 玄慈一听肯定火大了:"我靠, 凭什么是我变成她手下呀, 怎么不反过来? 我抗议!" 于是, 两人相约一战, 杀的是天昏地暗, 风云为之变色啊, 但是啊, 这场战争终究会有胜负, 胜者为王. 弱者就被吞并了. 反正谁加入谁效果是一样的, 门派就由两个变成一个了. 这段函数的意思明白了吧?
- void umite(int root1, int root2) // 虚竹和周芷若做朋友
- {
- int x, y;
- x = unionsearch(root1);// 我老大是玄慈
- y = unionsearch(root2);// 我老大是灭绝
- if(x != y)
- pre[x] = y; // 打一仗, 谁赢就当对方老大, 这里谁赢都一样, pre[y]=x 也行
- }
这样一来, 是否感觉关系太长, 效率也会大大降低
设想这样一个场景: 两个互不相识的大侠碰面了, 想知道能不能干一场. 于是赶紧打电话问自己的上级:"你是不是掌门?" 上级说:"我不是呀, 我的上级是谁谁谁, 你问问他看看." 一路问下去, 原来两人的最终 boss 都是东厂曹公公. "哎呀呀, 原来是自己人, 有礼有礼, 在下三营六组白面葫芦娃!" "幸会幸会, 在下九营十八组仙子狗尾巴花!" 两人高高兴兴地手拉手喝酒去了. "等等等等, 两位大侠请留步, 还有事情没完成呢!" 我叫住他俩. "哦, 对了, 还要做路径压缩." 两人醒悟. 白面葫芦娃打电话给他的上级六组长:"组长啊, 我查过了, 其实偶们的掌门是曹公公. 不如偶们一起结拜在曹公公手下吧, 省得级别太低, 以后查找掌门麻烦." "唔, 有道理." 白面葫芦娃接着打电话给刚才拜访过的三营长...... 仙子狗尾巴花也做了同样的事情. 这样, 查询中所有涉及到的人物都聚集在曹公公的直接领导下. 每次查询都做了优化处理, 所以整个门派树的层数都会维持在比较低的水平上. 路径压缩的代码, 看得懂很好, 看不懂可以自己模拟一下, 很简单的一个递归而已. 总之它所实现的功能就是这么个意思.
这样一来, 是不是能更加快速的找到自己的掌门呢
当然代码也能简单一些
findr 函数 查询 x 的掌门
- int findr(int x)// 找掌门
- {
- if(par[x]==x)// 找到了, 掌门出现
- return x;
- else
- return par[x]=findr(par[x]);// 我的上级不是掌门
- }
unite 函数也要改改
- void unite(int x,int y)//x 和 y 想打架
- {
- x=findr(x);// 我老大是 x
- y=findr(y);// 我老大是 y
- if(x==y)// 我们老大相同, 不打了
- return;
- par[y]=x;// 老大不同, 打一架, y 或 x 谁当老大都行, 反正最后是合并 y 并入 x 或 x 并入 y 都行
- sum[x]+=sum[y];//y 并入 x, 则 x 的小兵个数等于 x 的小兵个数 + y 的小兵个数
- }
OK 你已经学会如何处理帮派之间的纷争了 (并查集) 恭喜出师
可以试试这题 https://www.cnblogs.com/sky-stars/p/11222823.html
点个关注呗
来源: https://www.cnblogs.com/sky-stars/p/11222999.html