151. M-Coloring Problem

Given an undirected graph with n vertices (0-indexed) and m edges, and a number of available colors k, print 'Yes' if the graph's vertices can be colored using at most k colors such that no two vertices connected by an edge share a color, otherwise print 'No'.

Input: The first line contains the integer n (vertices). The second line contains the integer m (edges), followed by m lines each with two space-separated vertex indices for an edge. The final line contains the integer k, the number of available colors. Output: Print 'Yes' if the graph can be colored with at most k colors so no adjacent vertices share a color, otherwise print 'No'.

1 <= n <= 20, 0 <= m <= n*(n-1)/2

This problem only asks whether a valid coloring EXISTS (yes/no), not to find the MINIMUM number of colors needed (the true 'chromatic number', a much harder problem) - a fixed k is given, simplifying the search considerably compared to finding the optimal k.

Check whether a graph's vertices can be colored using at most k colors so that no two connected vertices share a color. Brute force: Try every possible assignment of colors to all n vertices directly (k^n total combinations) and check each one for validity - this is exponential and impractical for larger graphs, though feasible here given the small constraint (n<=20). Optimised: Checking each vertex's color choice against its ALREADY-COLORED neighbors immediately (rather than waiting to check the whole assignment at the end) prunes invalid branches as early as possible - most invalid color 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 complete assignment check all m edges to see whether any edge connects two same-colored vertices. If any assignment passes with no conflicting edge, print 'Yes'; otherwise print 'No'. This is guaranteed correct since it examines literally every possible coloring, but building and validating full assignments one at a time wastes effort on colorings that could have been ruled out much earlier. Time: O(k^n * m) Space: O(n)

Keep the same backtracking structure, but represent each vertex's adjacency as a bitmask (since n is at most 20 this fits comfortably in a machine integer), so checking whether a candidate color conflicts with any already-colored neighbor becomes a single bitwise AND instead of scanning a neighbor list. Additionally, order vertices by descending degree so the most constrained vertices are colored first, causing conflicts (and therefore pruning) to happen much earlier in the search. The worst-case exponential bound cannot be avoided for an NP-complete problem, but the per-node work drops to O(1) and the search tree explored in practice shrinks dramatically compared to naive backtracking. Time: O(k^n) worst case, with O(1) conflict checks per step Space: O(n)

Assign colors to vertices one at a time in a fixed order, and before committing to a color for the current vertex, check it only against the already-colored neighbors seen so far; if a conflict is found, abandon that color immediately and try the next one, backtracking entirely if no color works. This is still exponential in the worst case since graph coloring is NP-complete, but by rejecting bad partial assignments as early as possible it avoids ever completing (and then wastefully checking) most of the invalid colorings that brute force would fully construct. Time: O(k^n) worst case, far fewer in practice Space: O(n)

1. Try coloring vertices one at a time, in order 0 to n-1. 2. For each vertex, try every color 1 through k, but only proceed with a color if no already-colored NEIGHBOR (adjacent vertex) already has it. 3. Backtrack (remove the color and try the next) if a vertex runs out of valid colors to try; stop as soon as any complete valid coloring 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 array tracking each vertex's assigned color and the recursion stack.

Test m = 0 (no edges, any k >= 1 works), k = 1 (only works if there are no edges), and n = 20 (largest case, since coloring is exponential in the worst case).

Be ready to connect this to real-world graph coloring applications (scheduling conflicting exams/timeslots, register allocation in compilers, map coloring) - recognizing that many practical scheduling problems reduce to graph coloring is a valuable interview signal.