c889: 2. 二分圖

c889: 2. 二分圖

題 意:

一 個 圖 G 是 不 是 二 分 圖 可 以 判 斷 如 下。

我 們 試 著 將 G 中 的 每 一 個 頂 點 著 上 白 色 或 黑 色。

為 了 方 便 說 明，我 們 假 設 G 是 一 個 連 通 圖 (connected graph)，也 就 是 說 G 中 任 兩 個 頂 點 間 都 存 在 一 條 路 徑 : 

而 且 我 們 稱 白 和 黑 是 兩 個 對 立 的 顏 色。

開 始 時 我 們 任 選 一 頂 點 著 上 白 色，其 餘 所 有 頂 點 都 沒 有 顏 色。然 後 重 複 以 下 規 則 直 到 每 一 個 頂 點 都 被 著 上 顏 色 :

挑 一 個 有 顏 色 的 頂 點，將 所 有 和 它 相 鄰 的 頂 點 著 上 對 立 的 顏 色。

在 過 程 中 如 果發 現 一 個 已 經 有 顏 色 的 頂 點 因 為 (R) 這 個 規 則 必 須 被 著 上 不 同 的 顏 色，那 麼 就 出 現 了 矛 盾，G 不 是 二 分 圖，可 以 停 止 著 色。

請 判 斷 一 圖 是 否 為 二 分 圖，如 果 是 請 輸 出 兩 顏 色 頂 點 數 的 最 小 整 數 k。

若 非 則 輸 出 0。

solve:

bfs 中 紀 錄 每 個 點 的 顏 色。

因 為 不 一 定 是 連 通 圖，所 以 每 個 點 都 要 尋 訪 ( 尋 訪 過 的 不 用 再 bfs 一 次。)

code: