tags: APCS

d768－Bicoloring(BFS)

題目連結： d768

題目解析

這個問題是關於圖的二分圖判定問題。二分圖是一種可以使用兩種顏色塗色，且相鄰頂點之間顏色不同的圖。問題要求判斷給定的圖是否是二分圖。

解題方向

1. 圖的建模：
   • 圖中的節點用編號表示，從 0 到 n-1。
   • 邊的連接關係用鄰接表表示，color_map 是一個列表，列表的每個元素是一個節點所連接的所有其他節點。
2. 二分圖判定：
   • 使用 BFS（廣度優先搜索）來嘗試給圖中的節點塗色。
   • 初始時，我們可以隨便選擇一個節點塗上一種顏色，這裡用 1 表示第一種顏色，用 2 表示第二種顏色。
   • 對於每一個節點，查看它相鄰的節點。如果相鄰的節點還未塗色，就塗上與當前節點不同的顏色。如果相鄰的節點已經塗色，且顏色與當前節點相同，則該圖不是二分圖。
3. 輸出結果：
   • 如果 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
     ​​​​​​​​]
     

2. BFS 搜索：

   • 開始點：節點 0
   • 初始化訪問陣列 visit 為 [0, 0, 0, …, 0]（200個0），並將 visit[0] = 1（表示節點 0 被塗為顏色1）。

3. 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