Uva 10004 - Bicoloring

題目

Problem

給定任意的圖形,問可不可以在每個點上著不同兩種的顏色,並且相同顏色的點不相鄰。

  • 沒有自環
  • 無向圖
  • 強連通

想法

從起點(0)開始,DFS到終點,每次往下DFS時就把點圖上不同顏色,並且檢查相鄰的點,如果是相同顏色就回傳false,反之則true。

AC Code

https://github.com/roy4801/solved_problems/tree/master/uva/10004.cpp

推薦文章