网站展示型和营销型有什么区别,响应式网站建站平台,网站制作能赚多少钱,网站导航做外链目录 原因#xff1a;
优化#xff1a; 原因#xff1a;
当路径比较特殊#xff0c;如图#xff1a; 非常深#xff0c;最底层进行find时#xff0c;循环找根#xff08;或者递归找#xff09;#xff0c;消耗就比较大。
我们可以进行优化。
优化#xff1a; 优化 原因
当路径比较特殊如图 非常深最底层进行find时循环找根或者递归找消耗就比较大。
我们可以进行优化。
优化
arr就是并查集的数组
我们在find找到根时可以再来一次这次直接将arr里的上面节点直接换成根节点这样以后查找会非常快
但并非以后还是直接根节点因为根节点之后可能还会变此时处理不到底层节点底层节点可能就要多找一两次不过消耗很少了。
int find(int aim)
{int cur aim;while (arr[aim] ! aim){aim arr[aim];}//压缩://while (arr[cur] ! cur){int tmp cur;cur arr[cur];arr[tmp] aim;}/return aim;
} aim正好就是根了这个时候不要浪费就去压缩一下。
cur记下最开始根也是当前要处理的节点
因为要改掉他的arr所以提前用tmp把他的前驱节点(即上面的节点)记录下来以便可以继续压缩。然而这里不是。。这里的处理可以少写一句。这里是用tmp记下cur然后cur去成为下一个要处理的即他自己的前驱节点然后就可以对tmp操作了。
