克鲁斯卡尔有很多优美的性质，这道题就是利用了其中的一个。
如果把所有边权相同的划分为一个阶段，先做边权小的，再做边权大的。那么如果当前做第i个阶段，称前i个阶段的可以继续选一些边权更大的边构成最小生成树的选边方案为有效方案，前i-1个阶段无论哪种有效方案，各个联通块中的点一定是相同的，（但联通块中边可能不同）。把一个联通块中的点称为在一同个集合里面，那么不同有效方案的集合表示一定是相同的。为什么呢？因为如果两个有效方案的集合表示不同，则一定可以扩展任意一个有效方案的集合，使得他还能多选一条或多条边权较小的边（前i-1阶段的边）。与它是有效方案矛盾。
因此，只需枚举每种边权的边，然后2^10的搜索即可。用并查集实现，在进行每个阶段的搜索前，先用路径压缩把每个点的代表元找到。然后试探性的搜索时的并查集不能路径压缩，而记代表元的形式构成一棵树，回溯时只需把代表元指针指回来即可。