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