是的,這是一個 NP 的問題。意思也就是說,如果告訴你哪幾間房間是準備室的話,檢查這樣有無符合限制僅需要 P 的時間。(先檢查每條邊是否至少有一的頂點是準備室,檢查的時候順便將另外一個頂點標記,然後再檢查所有的頂點是不是都有標記或是自己就是準備室, n + m)
先看簡單一點的,如果整能有一間準備室。 那麼隨便挑一個邊,這個邊的兩邊至少有一個頂點得要是準備室。那先試試看把其中一個頂點當準備室,這樣合不合法,不行的話再把另外一個頂點當準備室看看合不合法。如果兩個放法都不行,這圖鐵定無解。
那麼如果可以擺放兩間準備室呢?隨便挑兩個沒有重疊到的邊 (v1, v2), (v3, v4) ,v1 ~ v4 都不相等,分別嘗試 [v1, v3], [v1, v4], [v2, v3], [v2, v4] 當準備室,如果這四種方法都不行,那這圖肯定無法解。
不管你取出哪兩條邊,只要這兩條邊的四個頂點都不相等,就可以得出這樣的推論。
我想嘗試說明的是,如果你能找出 8 的地方讓你選擇,每個地方必須保證一定會有一個準備室,那麼當你在這 8 個地方爆搜完後發覺還是無解的時候,你就可以肯定這絕對無解。那麼可能會花 2^8 (n + m) = 256(n + m) 。
實際上做的時候到也不用這麼麻煩 :)