M-Coloring Problem
Advanced Backtracking DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Graph Coloring Problem: Determining if a Graph Can Be Colored with at Most M Colors, Graph, Backtracking, Recursion, Time Complexity, Space Complexity, Adjacency Matrix, graph algorithms, graph theory, backtracking, Graph Theory, Graph Coloring.
Problem Statement: Given an undirected graph and a maximum number of colors M, determine if the graph can be colored with at most M colors such that no two adjacent vertices of the graph are colored with the same color. Input Specification: The input consists of: An integer N, representing the number of vertices in the graph. An integer M, representing the maximum number of colors allowed. An integer E, representing the number of edges. A list of E edges, where each edge is given as a pair (u, v) indicating an undirected edge between vertex u and vertex v. Vertices are 0 indexed. Output Specification: Return 1 if the graph can be colored as per the conditions, otherwise return 0. Examples: Example 1: Input: N = 4 M = 3 E = 5 Edges[] = { (0, 1), (1, 2), (2, 3), (3, 0), (0, 2) } Output: 1 Explanation: It is possible to colour the given graph using 3 colours. Example 2: Input: N = 3 M = 2 E = 3 Edges[] = { (0, 1), (1, 2), (0, 2) } Output: 0 Explanation: It is not possible to color.