投稿

并查集

Name: 并查集
Uploaded: 2018-07-06T08:05:57.000Z
Duration: 23 min 27 s
Channel: 人间提督

3320

2018-07-06 16:05:57

未经作者授权，禁止转载

c++实现并查集抱歉，不知道为什么视频漏了最后一点内容，就是找祖宗(father函数)中的优化。因为我们一个一个递归，辛辛苦苦找到祖宗之后，在a[x]中直接保存祖宗的序号就行了，这样下次查找时，就会快很多，这个叫做【路径压缩】。具体就是在father函数结束前，加入一行代码: a[x]=father(a[x]); 就行了。具体的思想，有点类似于记忆化搜索。

教学视频

自制

原创

学习

顶部