当然是不一样的, 你赋值是在findRoot中做的 set[s] = findRoot( set , set[s] ) ; 但是merge操作在findRoot后执行, 可能会改变root. 另外你这个赋值操作是一种并查集的优化方法, 称为路径压缩, 这样保证查找的路径不会过长, 复杂度为log级, 但并不能保证所有点都直接指向父节点, 否则查找就是稳定O(1)了. 实际上要达到近似常数的复杂度还需要使用按秩合并优化.
点赞 2

相关推荐

牛客网
牛客网在线编程
牛客网题解
牛客企业服务