d768-Bicoloring(DFS)
題目解析
這個問題要求我們判斷一個無向圖是否可以使用兩種顏色進行塗色,使得所有相鄰的節點顏色不同。這是一個典型的二分圖(Bipartite Graph)問題。
解題方向
解決這個問題的核心是利用深度優先搜索(DFS)進行圖的遍歷,並在過程中嘗試使用兩種顏色來塗色。如果在某個遞迴分支中發現相鄰的節點顏色相同,則可以判斷該圖不是二分圖,無法用兩種顏色塗色。
步驟:
- 初始化:建立圖的鄰接列表 G 以及一個用來標記節點顏色的列表 color。
- DFS 搜索與塗色:
- 開始從任意一個節點(通常是節點 0)進行 DFS 搜索,嘗試用兩種顏色來塗色。
- 每當訪問一個節點,嘗試將其塗成與父節點不同的顏色。
- 如果發現某個節點的顏色與預期衝突,則立即返回判斷該圖不能二分塗色。
- 結果輸出:
- 如果整個 DFS 遍歷過程中沒有出現顏色衝突,則該圖是二分圖,輸出 "BICOLORABLE."。
- 否則,輸出 "NOT BICOLORABLE."。
程式解析
- 圖的表示:
- G 是鄰接列表,用來表示圖中節點之間的連接關係。
- color 是用來存儲節點顏色的列表。初始化為 0 表示節點未被訪問過。
- DFS 函數:
- DFS(s, c) 函數用來遞迴地為節點塗色。
- color[s] = c 為節點 s 塗上顏色 c。
- min(isDiffColor, DFS(v, -c)) 確保如果在遞迴過程中任何一步發現顏色衝突(即 DFS(v, -c) 返回 0),isDiffColor 會被設為 0,並最終返回。
- 主循環:
- 依次讀取多組測試資料,對每組資料建立圖的結構並執行 DFS 來判斷是否可以二分塗色。
- 根據 DFS 返回值決定輸出 "BICOLORABLE." 或 "NOT BICOLORABLE."。
完整程式碼