---
title: 1042. Flower Planting With No Adjacent
tags: graph
description: share source code.
---

# 1042. Flower Planting With No Adjacent

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
      List<Integer>[] path = new ArrayList[n];
      Arrays.setAll(path, v -> new ArrayList<>());
      
      for(int [] p : paths){
        path[p[0] - 1].add(p[1] - 1);
        path[p[1] - 1].add(p[0] - 1);
      }
      
      int colors [] =  new int [n];
      Arrays.fill(colors, -1);
        
      boolean used [] =  new boolean [n + 1];  
    
      for(int i = 0; i < n; i++){
          
          if(colors[i] == -1){
            dfs( path , i, -1, colors, used, n);
          }
      }
        
      return colors;   
    }
    
    public void dfs(List<Integer>[] path , int u, int p,  int [] colors, boolean [] used, int n){
    

          
            boolean temp [] =  new boolean [5];    
            for(int v_ : path[u]){
                if(colors[v_] == -1){
                    continue;
                }
                temp[colors[v_]] = true;
              } 
            for(int i = 1; i <= 4; i++){
                if(!temp[i]){
                    colors[u] = i;
                }
            }
        
      
      for(int v : path[u]){
        if(v == p || p == -1)
          continue;
          
        dfs(path , v, u , colors, used, n);
      }
      
  }
}