###### tags: `APCS`
# **d768－Bicoloring(BFS)**
### **題目連結：** [**d768**](https://zerojudge.tw/ShowProblem?problemid=d768)
### **題目解析**
這個問題是關於圖的二分圖判定問題。二分圖是一種可以使用兩種顏色塗色，且相鄰頂點之間顏色不同的圖。問題要求判斷給定的圖是否是二分圖。
### **解題方向**
1. 圖的建模：
* 圖中的節點用編號表示，從 0 到 n-1。
* 邊的連接關係用鄰接表表示，color_map 是一個列表，列表的每個元素是一個節點所連接的所有其他節點。
1. 二分圖判定：
* 使用 BFS（廣度優先搜索）來嘗試給圖中的節點塗色。
* 初始時，我們可以隨便選擇一個節點塗上一種顏色，這裡用 1 表示第一種顏色，用 2 表示第二種顏色。
* 對於每一個節點，查看它相鄰的節點。如果相鄰的節點還未塗色，就塗上與當前節點不同的顏色。如果相鄰的節點已經塗色，且顏色與當前節點相同，則該圖不是二分圖。
1. 輸出結果：
* 如果 BFS 成功地塗色完成，則圖是二分圖，輸出 "BICOLORABLE."。
* 如果在塗色過程中發現某個節點和它的相鄰節點顏色相同，則圖不是二分圖，輸出 "NOT BICOLORABLE."。
### **程式解析**
1. 初始化與讀取輸入：

* 節點數 N = 3
* 邊數 M = 3
* 三條邊：
* 0 -> 1
* 1 -> 2
* 2 -> 0
* 這個圖的鄰接表 (color_map) 會是：

        color_map = [
            [1, 2],  # 0 接到 1 和 2
            [0, 2],  # 1 接到 0 和 2
            [1, 0]   # 2 接到 1 和 0
        ]

1. BFS 搜索：
* 開始點：節點 0
* 初始化訪問陣列 visit 為 [0, 0, 0, ..., 0]（200個0），並將 visit[0] = 1（表示節點 0 被塗為顏色1）。
1. BFS 過程：
* 步驟 1：
* 現在的節點：0，相鄰的節點是 1 和 2。
* 節點 1 和 2 還沒被塗色，分別塗為顏色 2（與節點0不同）。
* 將 1 和 2 加入隊列 Q。
* 此時 visit 陣列為 [1, 2, 2, ..., 0]。
* Q 為 [1, 2]。
* 步驟 2：
* 現在的節點：1，相鄰的節點是 0 和 2。
* 節點 0 已經塗色，且顏色與節點 1 不同（無需處理）。
* 節點 2 已經塗色，但顏色與節點 1 相同（發現相鄰節點顏色相同，回傳 False）。
* 程式輸出 "NOT BICOLORABLE."。
### **完整程式碼**

MAX_SIZE = 200

def BFS(color_map, start):
    Q = [start]
    visit = [0 for _ in range(MAX_SIZE)]

    visit[start] = 1  # 初始節點塗色為1

    while len(Q) > 0:
        now = Q.pop(0)

        for next_region in color_map[now]:
            if visit[next_region] == 0:  # 下一個節點還未訪問
                Q.append(next_region)
                visit[next_region] = 3 - visit[now]  # 塗與當前節點不同的顏色
            elif visit[next_region] == visit[now]:  # 若相鄰節點顏色相同
                return False  # 無法二分塗色

    return True

while True:
    try:
        N = int(input())
        if N == 0:
            break
        M = int(input())

        color_map = [[] for _ in range(MAX_SIZE)]

        for _ in range(M):
            u, v = map(int, input().split())
            color_map[u].append(v)
            color_map[v].append(u)

        result = BFS(color_map, 0)  # 從第0個節點開始進行BFS

        if result:
            print("BICOLORABLE.")
        else:
            print("NOT BICOLORABLE.")
    except:
        break