392. M-Colouring Problem

Given an undirected graph with n vertices (0-indexed), m edges, and a target number of colors k, determine whether the graph's vertices can be colored using at most k colors such that no two adjacent vertices share a color. Print 'Yes' if possible, otherwise 'No'.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, an undirected edge. The final line contains k, the target number of colors. Output: Print 'Yes' if the graph can be properly colored with at most k colors, otherwise print 'No'.

1 <= n <= 20

Stopping the moment the LAST vertex is successfully colored (rather than continuing to search for other valid colorings) is a simple but important early-exit optimization - once ANY valid coloring with k colors is found, the yes/no question is already fully answered.

Check whether a graph's vertices can be colored using at most a fixed number of colors, k, with no two adjacent vertices sharing a color. Brute force: Try every possible assignment of k colors to n vertices directly (k^n total combinations) and check each one - this is what backtracking effectively explores, but with the crucial difference of pruning invalid branches EARLY rather than generating and checking every full combination. Optimised: Checking each vertex's color choice against its ALREADY-COLORED neighbors IMMEDIATELY (rather than waiting to verify a complete assignment) prunes invalid branches as early as possible - most invalid combinations are caught and abandoned after just a few vertices, not after assigning colors to all n.

Generate every one of the k^n possible ways to assign one of k colors to each of the n vertices, and for each full assignment check every edge to see whether its two endpoints share a color, reporting 'Yes' the first time a fully valid assignment is found. This is guaranteed correct since it literally tries every possibility, but the number of colorings grows exponentially with n, making it usable only for tiny graphs. Time: O(k^n * (n+m)) Space: O(n)

Since n is at most 20, represent sets of vertices as bitmasks and first precompute which subsets of vertices form an independent set (no internal edges) - these are exactly the sets that could all legally share one color. Then run a DP over all 2^n subsets, where dp[mask] tracks the minimum number of colors needed to properly color exactly the vertices in mask, transitioning by peeling off one independent subset of mask at a time and taking dp[mask without that subset] + 1; finally check whether dp[full mask] <= k. This turns an otherwise exponential search into a structured subset DP that reuses work across overlapping subsets instead of re-deriving colorings from scratch, which is dramatically faster than raw backtracking at this size. Time: O(2^n * n) (with independent-set precomputation) Space: O(2^n)

Assign colors to vertices one at a time in a fixed order, and before recursing into the next vertex, check only that vertex's already-colored neighbors to make sure no conflict has been introduced, backtracking immediately whenever a color choice creates a conflict rather than waiting to check the whole assignment at the end. This prunes huge portions of the search tree compared to generating every coloring blindly, since invalid partial assignments are abandoned as early as possible, though the worst-case bound is still exponential for adversarial graphs. Time: O(k^n) worst case, far fewer in practice Space: O(n)

1. Backtrack vertex by vertex: try assigning each of the k colors to the CURRENT vertex, checking it against every already-colored NEIGHBOR. 2. Recurse if a color choice is valid; if EVERY color fails for some vertex, backtrack to the PREVIOUS vertex and try its next color instead. 3. The moment you successfully color the LAST vertex, stop immediately and report Yes - no need to explore further colorings once one is found.

Time: O(k^n) in the worst case, though heavily pruned in practice by the immediate neighbor-conflict checks. Space: O(n), for the color-assignment array and the recursion stack.

k = 1 with at least one edge present (always 'No'), a graph with no edges (always 'Yes'), and n at its maximum of 20 to confirm the backtracking search stays feasible.

Be ready to clearly distinguish this FIXED-k feasibility check from the 'find the MINIMUM number of colors' version of graph coloring (which tries increasing values of m and calls this exact feasibility check repeatedly) - this problem only needs a single yes/no answer for one given k, not a search over increasing k values.