1679

無向グラフが与えられるので、MSTのコストを求めたい。またMSTがユニークかどうか知りたい。という感じの問題。

MSTのコストはプリムでもクラスカルでもいいので適当に求めることができる。その後、使用した辺を一通り除去してみてもMSTのコストが変わらなければユニークではない。つまりノード数の数だけMSTを求めてみるだけ。