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