最小生成树(kruskal算法)

其他相关资料: 最小生成树prim算法 并查集+路径压缩 最小生成树模板题 先上原理图: 原理就是说贪心的从最小边(排个序就好了)找起,如果一条边两个顶点都已被找过(即两个顶点在同一个连通分量),则跳过该边(因为每次找边要确保有新顶点加入连通分量,若该边两个顶点都已被找过则这条边已经没有加入的意义)。但我们又怎么分辨两个顶点是否是来自同一连通分量呢,其实我们可以将一个连通分量看作一个集合,那么就可以用并查集来查询和合并连通分量。 附kruskal代码: int ly(int a){ if(head[a]==0) return a; return head[a]=ly(hea