Flower Planting With No Adjacent

Intuition

Solution

class Solution:
    def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(N)]
        for p, q in paths:
            adj[p - 1].append(q - 1)
            adj[q - 1].append(p - 1)
        colors = [None] * N
        for vertex in range(N):
            if colors[vertex] is None:
                self.dfs(adj, vertex, colors)
        return colors

    def dfs(self, adj, vertex, colors):
        # Using -1 to mark vertex which is visited but doesn't have color yet
        colors[vertex] = -1
        used = set()
        for child in adj[vertex]:
            if colors[child] is None:
                self.dfs(adj, child, colors)
            used.add(colors[child])
        for i in range(1, 5):
            if i not in used:
                colors[vertex] = i
                break