DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on

M - Coloring / Flower Planting With No Adjacent

Flower Planting With No Adjacent

const mColoring = (paths, n, m) => {
  let color = new Array(n).fill(0);
  let adj = [];
  for (let i = 0; i < n; i++) {
    adj[i] = [];
  }

  for (let i = 0; i < paths.length; i++) {
    let [to, from] = paths[i];
    adj[to].push(from);
    adj[from].push(to);
  }

  const isSafe = (node, nextColor) => {
    for (let i of adj[node]) {
      if (color[i] === nextColor) {
        return false;
      }
    }
    return true;
  };

  const solve = (node) => {
    if (node === n) {
      return true;
    }
    for (let i = 1; i <= m; i++) {
      if (isSafe(node, i)) {
        color[node] = i;
        if (solve(node + 1)) {
          return true;
        }
      }
    }
  };

  if (solve(0)) {
    console.log(color);
    return true;
  } else {
    return false;
  }
};
const edges = [
  [0, 1],
  [1, 2],
  [2, 3],
  [3, 0],
  [0, 2],
];
console.log(mColoring(edges, 4, 3));

const edges_1 = [
  [0, 1],
  [1, 2],
  [0, 2],
];

console.log(mColoring(edges_1, 3, 2));
Enter fullscreen mode Exit fullscreen mode

Top comments (0)