サーバーを頂点、ケーブルを辺とみなしたグラフを考えます。

連結成分ごとに、そこに属する頂点と、”余っている”辺を求めます。これはDFS/BFSを行うことや、DSUなどのデータ構造を用いることでできます。
“余っている辺”の端点を、別の連結成分に属する頂点に繋ぎ変えることで、必ず連結成分数を減らすことができます。逆にどのように辺を繋ぎ変えても \(1\) 回の操作では連結成分数は高々 \(1\) しか変化しないため、この操作を繰り返し行うことで操作回数を最小にできることがわかります。

“余っている辺”が多い連結成分から順に辺の繋ぎ変えを考えると実装が容易です。

writer解(C++)