STLighter
2016-10-20 01:59 电子科技大学 前端工程师
关注
当然是不一样的, 你赋值是在findRoot中做的
set[s] = findRoot( set , set[s] ) ;
但是merge操作在findRoot后执行, 可能会改变root.
另外你这个赋值操作是一种并查集的优化方法, 称为路径压缩, 这样保证查找的路径不会过长, 复杂度为log级,
但并不能保证所有点都直接指向父节点, 否则查找就是稳定O(1)了.
实际上要达到近似常数的复杂度还需要使用按秩合并优化.
查看原帖
点赞 2
相关推荐
11-21 13:08
蚌埠坦克学院 C++ 
投递金山WPS等公司10个岗位 > 点赞 评论 收藏
分享
10-18 13:02
西安理工大学 C++ 
点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
263688次浏览 2185人参与
# 0offer是寒冬太冷还是我太菜 #
887190次浏览 7909人参与
# 北方华创开奖 #
23658次浏览 260人参与
# 地方国企笔面经互助 #
2846次浏览 7人参与
# 学历or实习经历，哪个更重要 #
43408次浏览 328人参与
# 选完offer后，你后悔学本专业吗 #
13214次浏览 94人参与
# 查收我的offer竞争力报告 #
19495次浏览 255人参与
# 应届生被毁约被毁意向了怎么办 #
28183次浏览 243人参与
# 你最想要的公司福利是？ #
41843次浏览 146人参与
# 如何一边实习一边秋招 #
987306次浏览 12609人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3295次浏览 36人参与
# 嵌入式转岗的难度怎么样 #
11196次浏览 251人参与
# 你最希望上岸的公司是？ #
76514次浏览 469人参与
# 如何写一份好简历 #
604994次浏览 8508人参与
# 面试体验感最好的是哪家？ #
83639次浏览 818人参与
# 机械应届生薪资要多少才合适？ #
12538次浏览 61人参与
# 牛客十周岁生日快乐 #
48725次浏览 759人参与
# 你认为第一份工作重要吗 #
5444次浏览 49人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
79923次浏览 589人参与
# 秋招OC许愿 #
228160次浏览 1880人参与
# 来聊聊机械薪资天花板是哪家 #
65720次浏览 445人参与