并查集+kruskal

是题解,也许吧.

使用了Kruskal 算法

一般来说，求最小生成树的算法有两种：Kruskal算法和Prim算法。本题用的是Kruskal，Prim我其实也试过，结果翻车了（翻车代码我会放在最后），“荣获”了5个测试点AC，2个WA，3个TLE。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Kruskal运用了贪心的思想，其核心思想为：先选1条权值最小的边并连接，再选权值次小的（当然前提是不能构成环）……直到所有点连通为止。作为生成树，应当在cnt=N−1cnt=N-1cnt=N−1时成立（想必都能做到这题了，树是什么还是已经了解了吧）。一般此算法的时间复杂度为O(M2)O(M^2)O(M2)，在这题中会出现超时，但通过并查集压缩后，找根节点的时间复杂度变成了O(1)O(1)O(1)，时间复杂度也就降为O(M)O(M)O(M)，过了！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Prim用的思想也是贪心，同时类似于Dijkstra算法（其实我也不太会），大致方法为：让所有点开始时处于未标记的状态，每次更新能到达的点及最短路径，接下来过程的就只能靠你自己了…… 下面是我的翻车记录，别抄了，AK不了的，自己看数据代入时间复杂度（也就O(N2)O(N^2)O(N2)）吧。事先看了其他题解，基本上也都是用Kruskal做的。