DreamJudge1319_并查集
推荐阅读
- 并查集可以看作一棵棵树组成的森林
- 每棵树实际都为图的一个连通图
- 已知，有N个点，那么把所有点都连通的最少边为 N-1
- 由于这些树内部都是连通的，可以把这些树看成一个新的点，最后看有几个点，假设为M,那么最少需要M-1条边能把整个图变成一个连通图
- 程序的关键点：find() 函数 ，注意 fa[x] = find(fa[x])是进行路径压缩的功能。
- 初始化，每个点的父亲为本身
- 注意理解sum 是什么，sum 是记录，将两个树连接到一起的次数，也就是必不可少的边有多少个
- 而如果读入一条新的边，连接的是某棵树中的点之间的边，那么对于这条边对于整体的连通并没有什么作用。
- 只是在树这个点中的边，而对树组成的点集相连没有什么作用，所以不计算，其为对于连通可有可无的边
- sum 记录的是对于连通必不可少的边，那么我们最后才能用 N - sum -1 算出，最少还需多少边，图才能连通。
- 注意：find ()函数 ，初始化，读边判断连接，sum
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发