邢台如何做企业网站,百度营销推广登录,网站开发公司业务员培训,个人网站怎么做支付宝接口目录
前言
故事
#x1f33c;思路
#x1f33c;总结
#x1f33c;代码
#x1f44a;观察过程代码
#x1f44a;正确代码
#x1f44a;细节代码 来自《啊哈算法》
前言
刚学了树在优先队列中的应用--堆的实现
那么树还有哪些神奇的用法呢#xff1f;我们从一…
目录
前言
故事
思路
总结
代码
观察过程代码
正确代码
细节代码 来自《啊哈算法》
前言
刚学了树在优先队列中的应用--堆的实现
那么树还有哪些神奇的用法呢我们从一个故事说起----揭秘犯罪团伙 故事 快过年了犯罪分子们也开始为年终奖“奋斗”了小哼的家乡出现多次抢劫事件。 由于强盗人数过于庞大作案频繁警察想调查清楚到底有几个犯罪团伙实在不容易。 不过警察叔叔还是搜集到了几条线索 现在有10个强盗9条线索 1--2表示1号强盗与2号强盗是同伙
3--45--24--62--68--79--71--62--4 规定强盗同伙的同伙也是同伙你能帮警察叔叔查出有多少个独立的犯罪团伙吗 思路
要解决这个问题先假设10个强盗相互不认识他们各自为政每个人都是自己的头只听自己的
之后我们通过警察的线索一步步“合并同伙”
1声明一维数组
申请一个一维数组daddad[1] 1表示1号强盗的头是自己10号强盗的头是10号自己用dad[10] 10表示
2初始化
初始化dad数组当然书里是f数组 令 dad[i] i; 即可 3合并同伙
如果发现两个强盗是同伙那么他俩是同一犯罪团伙但是。。。谁做老大呢
我们假定左边的强盗更厉害些规定一个“靠左法则”比如警察得到的第一条线索是1号和2号同伙
1
所以1号在左边更厉害那么2号归顺1号也就是1号是2号的头头所以dad[2] 1;表示2号强盗的头是1号强盗 2
第二条线索3--43号强盗和4号是同伙根据“左边的更厉害”4号归顺3号所以 dad[4] 3; 3
第3条线索5--25号和2号强盗是同伙dad[5] 5说明5号强盗的头是自己
dad[2] 1说明2号强盗的头是1号强盗
根据“左边的更厉害”此时应该让2号归顺5号那么“1号强盗”就不干了“你凭什么抢我的人”
于是这俩强盗差点打起来了这让2号为难了2号归顺5号还是继续跟着原来的头1号呢 这里我们还是按左边的更厉害的原则5号强盗直接找2号的头1号谈让1号这个老大也归顺他(递归实现) 操作dad[1] 5; dad[2] 5; 为什么在1号这个老大归顺5号后还要再让2号归顺一次呢
这一步不是必须的但会提高后面找强盗最高领导人的速度也就是找树的祖先的速度
否则很容易形成单支树结构一长条。。。极大浪费空间和时间 dad[2] 5; 这看似多余的一步也叫路径压缩不要觉得名字很高大上其实就是一行代码的事 第四条线索
4--6这俩同伙
此时dad[4] 3, dad[6] 6我们让6号强盗加入“3号犯罪团伙”即dad[6] 3; 第5条线索
2--6
此时dad[2] 5, dad[6] 3
我们令6号和他的老大都归顺“5号犯罪团伙”(递归实现)dad[6] 5; 以及 dad[3] 5; 第6条线索
8--7
此时dad[8] 8, dad[7] 7, 让7号归顺8号好了dad[7] 8; 第7条线索
9--7
此时dad[9] 9, dad[7] 8所以8号和7号都归顺9号强盗(路径压缩)(递归实现)
dad[8] 9; dad[7] 9; 除了让7号的老大归顺9号我们还让7号也直接归顺9号这一步叫路径压缩这一步通过递归返回时实现不会增加时间复杂度 第8条线索
1--6
此时dad[1] 5, dad[6] 5已经是同伙了不需要操作
第9条线索
2--4
此时dad[2] 5, dad[4] 3
4号归顺3号3号归顺5号5号归顺自己所以5号是最高领导人 从4号顺藤摸瓜到5号最高领导人的过程就是递归 递归完后dad[4] 5; 至此所有线索分析完毕那么有多少个犯罪团伙呢 由上图可知3个团伙 5号犯罪集团521346组成 9号犯罪集团987组成 10号犯罪集团10组成 容易知道如果 dad[i] i表示 i 号强盗是一个团伙的最高领导人最后数组dad中
dad[5] 5, dad[9] 9, dad[10] 10所以共3个犯罪团伙
总结 我们刚才模拟的是并查集算法并查集通过一个一维数组实现本质是维护一个森林。
初始森林每个点都是孤立的也就是每个强盗的老大都是自己也可以理解为每个点就是一棵只有一个节点的树
之后将这些孤立的点合并成一颗大树合并的过程就是叫爸爸的过程
叫爸爸的过程遵循“左边更厉害”和“擒贼先擒王”的原则
“擒贼先擒王”也就是先让老大归顺左边的强盗自己再归顺自己再归顺就是路径压缩 补充: 并查集也称为为不相交集数据结构 代码
观察过程代码
#includeiostream
using namespace std;
int dad[100];int Find(int x) //不停认老大, 直到顶头上司
{if(dad[x] x) return x;else {//路径压缩, 将路径上所有点的上级都设置为根节点dad[x] Find(dad[x]);return dad[x];}
}void join(int x, int y) //合并两个团伙
{//m为x的最高领导人, n为y的最高领导人int m Find(dad[x]), n Find(dad[y]);if(m ! n) //路径压缩dad[n] m; //第2个最高领导人认第1个当老大
}int main()
{for(int i 1; i 10; i)dad[i] i; //初始化自己为老大int a, b;for(int i 1; i 9; i) {cout第i条线索;cinab;join(a, b); //合并团伙coutdad[a] dad[b]endl;}int ans 0;for(int i 1; i 10; i)if(dad[i] i)ans 1;return 0;
}第1条线索1 2
1 1
第2条线索3 4
3 3
第3条线索5 2
5 1
第4条线索4 6
3 3
第5条线索2 6
1 3
第6条线索8 7
8 8
第7条线索9 7
9 8
第8条线索1 6
5 3
第9条线索2 4
1 3 为什么第一次没实现路径压缩呢就是虽然团伙总数确定了但是每个人依然跟着自己原来的老大没有跟着顶头上司 原来是代码第18行 m Find(dad[x]), n Find(dad[y]); 应该改成 m Find(x), n Find(y); 否则只是令右老大归顺了左老大但是右小弟没有直接归顺左老大右小弟依然跟着右老大 这样就没起到路径压缩的效果 正确代码
即使是正确代码《啊哈算法》里也存在BUG不过无关痛痒而已对时间复杂度几乎没影响
#includeiostream
using namespace std;
int dad[100];int Find(int x) //不停认老大, 直到顶头上司
{if(dad[x] x) return x;else {//路径压缩, 将路径上所有点的上级都设置为根节点dad[x] Find(dad[x]); //递归返回return dad[x];}
}void join(int x, int y) //合并两个团伙
{//m为x的最高领导人, n为y的最高领导人int m Find(x), n Find(y);if(m ! n) //路径压缩dad[n] m; //第2个最高领导人认第1个当老大
}int main()
{for(int i 1; i 10; i)dad[i] i; //初始化自己为老大int a, b;for(int i 1; i 9; i) {cinab;join(a, b); //合并团伙}int ans 0;for(int i 1; i 10; i)if(dad[i] i)ans 1;for(int i 1; i 10; i)cout第i个强盗的老大是dad[i]endl;cout共有ans个犯罪团伙;return 0;
}1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
第1个强盗的老大是5
第2个强盗的老大是5
第3个强盗的老大是5
第4个强盗的老大是5
第5个强盗的老大是5
第6个强盗的老大是5
第7个强盗的老大是8
第8个强盗的老大是9
第9个强盗的老大是9
第10个强盗的老大是10
共有3个犯罪团伙 上述代码实现了路径压缩但是第7个强盗的老大怎么还是8呢不应该是9吗 因为这种较为简单的路径压缩有一个小小的缺陷
需要第一次先找到祖宗第二次才能对路径上的节点进行压缩而输入9 7前7原来的老大是88的原来的老大也是8当输入9 7后进行join()函数
此时7的老大8号就归顺了9号但7的老大依然是8号没有变成9号需要在下一次递归查找老大时7的老大才变成9号但此时已经没有下次了 当然我们也可以在join()函数的最后重写一次 n Find(y) 就可以实现书里的效果但是不知道这样是否会影响时间复杂度 细节代码
#includeiostream
using namespace std;
int dad[100];int Find(int x) //不停认老大, 直到顶头上司
{if(dad[x] x) return x;else {//路径压缩, 将路径上所有点的上级都设置为根节点dad[x] Find(dad[x]); //递归返回return dad[x];}
}void join(int x, int y) //合并两个团伙
{//m为x的最高领导人, n为y的最高领导人int m Find(x), n Find(y);if(m ! n) //路径压缩dad[n] m; //第2个最高领导人认第1个当老大n Find(y); //重写一次
}int main()
{for(int i 1; i 10; i)dad[i] i; //初始化自己为老大int a, b;for(int i 1; i 9; i) {cinab;join(a, b); //合并团伙}int ans 0;for(int i 1; i 10; i)if(dad[i] i)ans 1;for(int i 1; i 10; i)cout第i个强盗的老大是dad[i]endl;cout共有ans个犯罪团伙;return 0;
}1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
第1个强盗的老大是5
第2个强盗的老大是5
第3个强盗的老大是5
第4个强盗的老大是5
第5个强盗的老大是5
第6个强盗的老大是5
第7个强盗的老大是9
第8个强盗的老大是9
第9个强盗的老大是9
第10个强盗的老大是10
共有3个犯罪团伙
