贪玩银耳汤

文章
4
资源
0
加入时间
2年10月17天

PTA-最小生成树的唯一性-(最小生成树的边权地位)

最小生成树的唯一性题意:就是给你n点个m条边,问你是否能这个图的最小生成树是唯一的,如果唯一输出最小生成树的权值,不唯一输出一共有多少连通块。思考:其实乍一看判断最小生成树是否唯一感觉像是见过,但是怎么也想不到,那就是没做过,只是见过罢了。然后我就想,是否唯一该怎么判断呢,之前做过两道都是用最小生树相同边权的地位都是相同的性质,我感觉如果在合并之前有res个边需要用,但是到了合并的时候只有res_t个了,也就是某些边可以用可以不用,只要出现这种情况那么这个最小生成树就不是唯一的。其余的操作就很简