###### tags: `APCS`
# **d768－Bicoloring(DFS)**
### **題目連結：** [**d768**](https://zerojudge.tw/ShowProblem?problemid=d768)
### **題目解析**
這個問題要求我們判斷一個無向圖是否可以使用兩種顏色進行塗色，使得所有相鄰的節點顏色不同。這是一個典型的二分圖（Bipartite Graph）問題。
### **解題方向**
解決這個問題的核心是利用深度優先搜索（DFS）進行圖的遍歷，並在過程中嘗試使用兩種顏色來塗色。如果在某個遞迴分支中發現相鄰的節點顏色相同，則可以判斷該圖不是二分圖，無法用兩種顏色塗色。

步驟：
1. 初始化：建立圖的鄰接列表 G 以及一個用來標記節點顏色的列表 color。
1. DFS 搜索與塗色：
* 開始從任意一個節點（通常是節點 0）進行 DFS 搜索，嘗試用兩種顏色來塗色。
* 每當訪問一個節點，嘗試將其塗成與父節點不同的顏色。
* 如果發現某個節點的顏色與預期衝突，則立即返回判斷該圖不能二分塗色。
1. 結果輸出：
* 如果整個 DFS 遍歷過程中沒有出現顏色衝突，則該圖是二分圖，輸出 "BICOLORABLE."。
* 否則，輸出 "NOT BICOLORABLE."。
### **程式解析**
1. 圖的表示：
* G 是鄰接列表，用來表示圖中節點之間的連接關係。
* color 是用來存儲節點顏色的列表。初始化為 0 表示節點未被訪問過。
1. DFS 函數：
* DFS(s, c) 函數用來遞迴地為節點塗色。
* color[s] = c 為節點 s 塗上顏色 c。
* min(isDiffColor, DFS(v, -c)) 確保如果在遞迴過程中任何一步發現顏色衝突（即 DFS(v, -c) 返回 0），isDiffColor 會被設為 0，並最終返回。
1. 主循環：
* 依次讀取多組測試資料，對每組資料建立圖的結構並執行 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