プログラミング問題集解答例（問３０）

import copy
def question30(neighbor_matrix):
    colors = {}
    for i in range(len(neighbor_matrix)):
        if i in colors.keys():
            continue
        colors[i] = 0
        queue = []
        for j in range(len(neighbor_matrix)):
            if neighbor_matrix[i][j] == 1:
                colors[j] = 1
                queue.append([i, j])

        while len(queue) > 0:
            path = queue.pop(0)
            #print(path)
            for j in range(len(neighbor_matrix)):
                if neighbor_matrix[path[-1]][j] == 1:
                    if j in colors.keys(): #and path[-1] in colors.keys():
                        if colors[path[-1]] == colors[j]:
                            #print(path[-1], j)
                            #print(colors)
                            return False
                    elif colors[path[-1]] == 1:
                        colors[j] = 0
                    else:
                        colors[j] = 1
                    path_new = copy.deepcopy(path)
                    if j not in path_new:
                        path_new.append(j)
                        queue.append(path_new)
            #print(path, path_new, queue)
    #print(colors)
    return True

n =  5
G = \
[[0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 0, 0, 0],
 [0, 1, 0, 0, 1],
 [1, 0, 0, 1, 0]]

question30(G)

True

n =  5
G = \
[[0, 1, 0, 0, 0],
 [1, 0, 0, 1, 1],
 [0, 0, 0, 0, 0],
 [0, 1, 0, 0, 1],
 [0, 1, 0, 1, 0]]

question30(G)

False

n =  8
G = \
[[0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 0],
 [0, 1, 1, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 1],
 [1, 0, 0, 1, 0, 0, 1, 1],
 [0, 0, 0, 0, 1, 1, 0, 0],
 [0, 0, 0, 0, 1, 1, 0, 0]]

question30(G)

True

n =  8
G = \
[[0, 1, 1, 0, 1, 0, 0, 0],
 [1, 0, 1, 0, 0, 0, 0, 1],
 [1, 1, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 1, 1, 0],
 [1, 0, 0, 0, 0, 0, 1, 0],
 [0, 0, 0, 1, 0, 0, 0, 1],
 [0, 0, 0, 1, 1, 0, 0, 0],
 [0, 1, 0, 0, 0, 1, 0, 0]]

question30(G)

False