Problems178
Search for a command to run...
Colour a graph so no edge joins equal colours
Initialization
Colour the nodes one at a time, 0 upwards, trying colours 1–3 at each. A colour is only allowed if no already-coloured neighbour is using it.
Backtracking
1function isSafe(col, node, colors, adj) {2 for (const neighbor of adj[node]) {3 if (colors[neighbor] === col) return false;4 }5 return true;6}7 8function solve(node, m, n, colors, adj) {9 // Every node coloured10 if (n === node) return true;11 12 for (let i = 1; i <= m; i++) {13 if (isSafe(i, node, colors, adj)) {14 colors[node] = i;15 if (solve(node + 1, m, n, colors, adj)) return true;16 colors[node] = 0; // undo17 }18 }19 return false;20}21 22function graphColoring(edges, m, n) {23 const adj = Array.from({ length: n }, () => []);24 for (const edge of edges) {//n: 4m: 3edges: 525 adj[edge[0]].push(edge[1]);26 adj[edge[1]].push(edge[0]);27 }28 const colors = new Array(n).fill(0);29 return solve(0, m, n, colors, adj);30}