問題:D - Forest
解答:Submission #10116025 - AtCoder Petrozavodsk Contest 001
メモ:森がnfor個あったとすると、その森を連結にするにはnfor-1個の辺を追加する必要がある。
このとき、2 * nfor - 2個の頂点を選ぶ必要があり、nfor個の頂点は各木で最もa[i]が小さいものを選び、のこりのnfor-2個の頂点は全ての頂点の中からa[i]が小さい順(ただし各木で最もa[i]が小さいのは除く)に選べばよい。
特殊ケース
- n < 2 * nfor - 2(頂点数が足らず、森を連結にできない)
- nfor = 1 (全体がすでに連結)