元のグラフの連結成分の数を \(c\) としたとき，\(c - 1\) 回の操作を行う必要があります．よって，余分な辺を事前に \(c - 1\) 辺選んでおきます（Union-Find を用意し，\(1\) 辺ずつ追加して連結成分を管理した際に，辺の両端が連結な場合に「余分な辺」であるとみなす，とすると簡潔に行えます）．

あとは，その \(c - 1\) 辺をつなぎかえることで全体を連結にしていきます．これについては，先ほどの Union-Find を用いることで，次のように行えばよいです．

1. まず，連結成分の代表元の番号を管理する集合 \(S\)（C++ の set などで実現可能です）を用意する．この集合を，\(c\) 個の連結成分の代表元で初期化する．
2. 余分な辺の中でまだ選んでいないものを \(1\) つ選ぶ．その辺が含まれる連結成分の代表元を，\(S\) から削除する．ここで \(S\) から削除された代表元を \(r_1\) とする．
3. \(S\) に含まれる要素を \(1\) つ，任意に選ぶ．その要素を \(S\) から削除する．これを \(r_2\) とする．
4. 2 で選んだ辺の両端の頂点のうち，片方の頂点の結ぶ先を \(r_2\) に変更する．ここで，Union-Find のマージに相当する操作を，\(r_1\) および \(r_2\) に対して行う．そうしてできた新たな連結成分の代表元 \(r_3\) を，\(S\) に追加する．
5. 2 から 4 までを規定の回数に到達するまで繰り返し行う．

なお，4 の操作において，マージ後の新たな代表元は ACL の dsu を用いると，merge 関数の返り値として得られることを利用し，r_3 = tree.merge(r_1, r_2) のように記述すると便利です．