Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Scamming the coding interview
- """
- def color_graph(graph_adjacency, number_of_vertices):
- # First vertex gets the first color
- vertex_to_color_map = {
- 0: 0
- }
- for i in range(1, number_of_vertices):
- neighbours = graph_adjacency[i]
- available_colors = [True for i in range(0, number_of_vertices)]
- for n in neighbours:
- color_of_neighbour = vertex_to_color_map.get(n)
- if color_of_neighbour is not None:
- available_colors[color_of_neighbour] = False
- # look for the first color that's available
- first_available_color = None
- for temp, color in enumerate(available_colors):
- if color:
- first_available_color = temp
- break
- if first_available_color is not None:
- vertex_to_color_map[i] = first_available_color
- return vertex_to_color_map
- if __name__ == '__main__':
- graph_adjacency_list = {
- 0: [1, 2],
- 1: [0, 2, 3],
- 2: [0, 1, 3],
- 3: [1, 2, 4],
- 4: [3]
- }
- max_colors_allowed = 3
- vertex_to_color_map = color_graph(graph_adjacency_list, 5)
- number_of_colors_used = len(set(vertex_to_color_map.values()))
- print(number_of_colors_used <= max_colors_allowed)
Add Comment
Please, Sign In to add comment