連結とは限らないグラフが与えられる場合、それを連結成分に分けた時に異なる連結成分が互いに影響を与えないことがよくある その場合、まず連結成分に分けてから個別に解けば「連結なグラフである」という制約が加わって解きやすくなる 連結であるなら例えば 全域木がある 辺がV-1本以上 辺がV-1本なら木である 問題変換