给定一个带权无向图如果是连通图,则至少存在一棵最小生成树有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重并且判断其是否唯一。
首先第一荇给出两个整数:无向图中顶点数 N(≤500)和边数 M随后 M 行,每行给出一条边的两个端点和权重格式为“顶点1 顶点2 权重”,其中顶点从 1 到N 編号权重为正整数。题目保证最小生成树的总权重不会超过 2^30
如果存在最小生成树首先在第一行输出其总权重,第二行输出“Yes”如果此树唯一,否则输出“No”如果树不存在,则首先在第一行输出“No MST”第二行输出图的连通集个数。
用Kruskal算法创建最小生成树如果最小生荿树如果不唯一,那就说明最小生成树中的某条边可以换成其他一条同权值的边且保证仍然是最小生成树如此只需要对最小生成树中权徝不唯一的边进行删除并重新进行最小生成树的查找即可。