Kruskal的经典扩展

acw348

Kruskal的经典扩展

题意：将一棵树扩展成一个完全图，保证该树是图的唯一最小生成树

关键思想：将一棵树看成是点集由集合合并组成的，每一次集合合并，都建构两个集合之间除树边以外的图边，由Kru算法的原来可知，最短的图边长度是w+1；

Code：