1.拿到一个题,如果可能是用最小生成树做,但是题目中没有说 所有点之间是连通的,
那我们不能看成整体连通,而应该看成连通块
必须是题目中说了,所有点之间是连通的才能看成一个整体!
如果是用最小生成树做的题,这个情况下就要 用kruskal,
因为多个联通块求最小生成树,是一个 “最小生成森林”
2.如何判定一个集合是否联通?
来自acwing 1142 题解的一部分,有这样的:
所以,我们可以用 BFS,DFS, 并查集,最小生成树来判断联通性。
3.如何求有多少个联通块?
来自acwing 1145 北极通讯网络