POJ 1679 The Unique MST

正文索引 [隐藏]

传送门:http://vjudge.net/problem/17124

题目大意

判读一个 N 个点 M 条边的图的最小生成树是否唯一,唯一则输出最小生成树。

题解

第一种方法:
最小生成树至少有一条边与次小生成树不一样。所以最小生成树之后枚举去掉最小生成树里的一条边,再做最小生成树看看答案是否相同,相同则不唯一。
第二种方法:
枚举不在最小生成树上的一条边(u,v),删除最小生成树中 u ~ v 边权最大的边,并且将 (u,v) 加入最小生成树

代码