M Coloring Problem

Hard

Colour a node, check its neighbours, backtrack

Problem

Given a graph and m colors, return whether the graph can be colored so no two adjacent nodes share a color.

In simple words

Try colouring each node with 1..m, backtracking whenever a neighbour already wears that colour.

The idea

Colour the nodes one at a time; for each, try every colour that no already-coloured neighbour uses. If no colour fits, back out and recolour the previous node. The check is local — only adjacent nodes matter — which is what makes the pruning cheap.

The trick

Only test the current node's neighbours; everything before it is already consistent.
Success is colouring the last node; failure is exhausting all m colours at some node.
Ordering nodes by degree first prunes far more branches, far earlier.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(m^V)spaceO(V)

1color(node):2  if node==V: return true3  for c in 1..m:4    if safe(node,c): assign; if color(node+1): true; unassign5  return false

Input

array: [2]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n=4, edges=[[0,1],[1,2],[2,3],[3,0],[0,2]], m=3
Output:: true
Explanation:: 3 colours suffice for this graph.

Example 2

Input:: n=3, edges=[[0,1],[1,2],[0,2]], m=2
Output:: false
Explanation:: A triangle needs 3 colours → false.

Example 3

Input:: n=2, edges=[[0,1]], m=2
Output:: true
Explanation:: Two nodes, two colours.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.