给定一个带权无向图,如果是连通图,则至少存在一棵最小生成树,有时最小生成树并不唯一。本题就要求你计算最小生成树的总权重,并且判断其是否唯一。 输入格式: 首先第一行给出两个整数:无向图中顶点数 N(≤500)和边数 M。随后 M 行,每行给出一条边的两个端点和权重,格式为“顶点1 顶点2 权重”,其中顶点从 1 到N 编号,权重为正整数。题目保证最小生成树的总权重不会超过 230。 输出格式: 如果存在最小生成树,首先在第一行输出其总权重,第二行输出“Yes”,如果此树唯一,否则输出“No”。如果树不存在,则首先在第一行输出“No MST”,第二行输出图的连通集个数。 请给出时间复杂度
时间: 2024-02-29 22:54:48 浏览: 49
tt.rar_M?n_无向图环_无向连通图 最小生成树_连通图
对于 Kruskal 算法,时间复杂度为 $O(M\log M)$,Prim 算法的时间复杂度为 $O(N^2)$ 或 $O(M\log N)$,其中 $M$ 表示边数,$N$ 表示顶点数。判断最小生成树是否唯一可以使用倍增法或 Tarjan 算法,时间复杂度为 $O(M\log N)$ 或 $O(M+N)$。因此总时间复杂度为 $O(M\log M)$ 或 $O(M\log N + N^2)$。
阅读全文