各連結成分について最小値を定めると、残りの値は一意に定まります。
そこで、全ての連結成分について最小値を決め打つことを考えます。

これをそのまま実装すると、孤立点が \(N\) 個与えられたときに計算量が \(\Omega(N!)\) となり、TLEします。
しかし、孤立点が \(2\) 個以上あるとき、どちらの孤立点も明らかに一意に定まりません。 そこで、孤立点が \(2\) 個以上あるときは孤立点を全て取り除いてから最小値を決め打つとします。
この時の計算量は \(O(N!!)\) であり、十分に高速です。

計算量解析について

まず、孤立点が \(1\) 個以下であるとき、連結成分は \(\frac{N}{2}\) 個以下です。
孤立点が \(1\) 個あるときは最後に残った値を割り振ると定めると、全ての連結成分は大きさが \(2\) 以上として構いません。
この時、最初の連結成分に入れる値の候補は高々 \(N\) 通り、次の候補は高々 \(N-2\) 通り……と候補が少なくとも \(2\) 個以上減るので、決め打ちに必要な計算量は \(O(N!!)\) と求められます。