day54 | 简单并查集

几个操作

  • find(u)

查找一个元素 u 的 root。 其中向上的过程可能会有多个层级,由于我们找到了最后的 root,通过root[u]=find(root[u])这个方法可以避免后续遍历过多的层级。

  • join(start,end)

把两个节点关联在一起。

  • 首先查询两个点的 root 点,如果相同则不用关联
  • 不关联则将查询到的 2 个 root 点关联起来。 注意的是不能直接讲 start 和 end 关联在一起(因为我们构造的都是一个全部指向 root 的有向图,此时 start 会有两个指向,原有 start 节点和 end 节点(用数组存储的话只有一个指向,相当于修改了start 的 root 节点))

全部评论

相关推荐

CrazyBucket:我今天下午也做梦在招聘会上面试一家小厂,给自己气笑了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务