No.330

$A$ をグラフの隣接行列とし, $D$ を対角成分がグラフの次数を表すとしたとき, $L = D - A$ はラプラシアン行列になる.

ラプラシアン行列の固有値の数はグラフの連結部分の数になる.

本問題は逆にラプラシアン行列が与えられるので, ここからグラフの連結部分の数を求める問題となる.

…というスペクトラムグラフ理論という分野があるらしい. (よくわからない)

連結部分の数を求めるには Union-Find を使えばいい.