Try   HackMD
tags: APCS

d768-Bicoloring(DFS)

題目連結: d768

題目解析

這個問題要求我們判斷一個無向圖是否可以使用兩種顏色進行塗色,使得所有相鄰的節點顏色不同。這是一個典型的二分圖(Bipartite Graph)問題。

解題方向

解決這個問題的核心是利用深度優先搜索(DFS)進行圖的遍歷,並在過程中嘗試使用兩種顏色來塗色。如果在某個遞迴分支中發現相鄰的節點顏色相同,則可以判斷該圖不是二分圖,無法用兩種顏色塗色。

步驟:

  1. 初始化:建立圖的鄰接列表 G 以及一個用來標記節點顏色的列表 color。
  2. DFS 搜索與塗色:
    • 開始從任意一個節點(通常是節點 0)進行 DFS 搜索,嘗試用兩種顏色來塗色。
    • 每當訪問一個節點,嘗試將其塗成與父節點不同的顏色。
    • 如果發現某個節點的顏色與預期衝突,則立即返回判斷該圖不能二分塗色。
  3. 結果輸出:
    • 如果整個 DFS 遍歷過程中沒有出現顏色衝突,則該圖是二分圖,輸出 "BICOLORABLE."。
    • 否則,輸出 "NOT BICOLORABLE."。

程式解析

  1. 圖的表示:
    • G 是鄰接列表,用來表示圖中節點之間的連接關係。
    • color 是用來存儲節點顏色的列表。初始化為 0 表示節點未被訪問過。
  2. DFS 函數:
    • DFS(s, c) 函數用來遞迴地為節點塗色。
    • color[s] = c 為節點 s 塗上顏色 c。
    • min(isDiffColor, DFS(v, -c)) 確保如果在遞迴過程中任何一步發現顏色衝突(即 DFS(v, -c) 返回 0),isDiffColor 會被設為 0,並最終返回。
  3. 主循環:
    • 依次讀取多組測試資料,對每組資料建立圖的結構並執行 DFS 來判斷是否可以二分塗色。
    • 根據 DFS 返回值決定輸出 "BICOLORABLE." 或 "NOT BICOLORABLE."。

完整程式碼

MAX_SIZE = 200 G = [ [] for i in range(MAX_SIZE) ] color = [ 0 for i in range(MAX_SIZE) ] def DFS(s, c): color[s] = c isDiffColor = 1 # 初始假設可以二分塗色 for v in G[s]: # 遍歷與節點 s 相連的所有節點 v if color[v] == 0: # 如果節點 v 尚未被塗色 isDiffColor = min(isDiffColor, DFS(v, -c)) # 遞迴並嘗試用相反的顏色塗色 elif color[v] == color[s]: # 如果節點 v 與節點 s 顏色相同,出現衝突 return 0 # 無法二分塗色,返回 0 return isDiffColor # 返回結果(1 或 0) # 主程序循環處理多組測試數據 while True: try: N = int(input()) # 節點數量 if N == 0: # 如果節點數量為 0,結束輸入 break M = int(input()) # 邊數量 for i in range(M): u, v = map(int, input().split()) G[u].append(v) G[v].append(u) ans = DFS(0, 1) # 從節點 0 開始,使用顏色 1 if ans == 1: print("BICOLORABLE.") else: print("NOT BICOLORABLE.") except: break