首页 > 代码库 > 并查集的 路径压缩(递归和非递归)
并查集的 路径压缩(递归和非递归)
这里的思路是 在每一次的找父亲节点的时候我们把每一个孩子的父亲的改成他的祖先。因为有可能一个孩子的关系很复杂可能就是一条链,这样查找就没浪费时间。//这是简单的递归实现find (int x){ while(x!=father[x]) father[x] = find(father[x]) ; return father[x] ;}//这是非递归的find (int x){ int r = x ; while(r != father[r])//找到r的祖先节点 r = father[r] ; int k = x ; while(k!father[k]) { father[k] = r ; k = father[x] ; x = k ; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。