Class Solution

Python/1042_FlowerPlantingwithNoAdjacent.py:17–34

'''
from collections import defaultdict
class Solution:
    def gardenNoAdj(self, N, paths):

        #Create Graph
        graph = defaultdict(list)
        for i in paths:
            graph[i[0]].append(i[1])                #Since Graph is Bidirectional, we need to add edge both sides
            graph[i[1]].append(i[0])
        flowers = []
        for i in range(1, N + 1):                   #We will traverse every node one by one
            choice = [1, 2, 3, 4]                   #create a fresh new list of choices of flowers
            for k in graph[i]:                      #check its neighbours
                try:
                    choice.remove(flowers[k-1])     #if any of the neighbour has been assigned flower (say flower 'X') we will remove that flower ('X')
                except:
                    pass
            flowers.append(choice[0])               #Select the first flower from the remaining choices
        return flowers