JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

L19 M-Coloring Problem

Given an undirected graph and an integer M. The task is to 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. Here coloring of a graph means the assignment of colors to all vertices. Print 1 if it is possible to colour vertices and 0 otherwise.

Example 1:
Input: N = 4
M = 3
E = 5
Edges[] = {(0,1),(1,2),(2,3),(3,0),(0,2)}
Explanation: Output 1 Explanation: It is possible to colour the given graph using 3 colours.

Example 1:
Input: N = 3 M = 2
E = 3
Edges[] = {(0,1),(1,2),(0,2)}
Output: 0

Constraints:
- 1 ≤ N ≤ 20
- 1 ≤ E ≤ (N*(N-1))/2
- 1 ≤ M ≤ N

Notes

Note: Zoom for Better Understanding

Intuition:

Is safe function returns true if it is possible to color it with that color i.e none of the adjacent nodes have the same color.

In case this is an algorithm and follows a certain intuition, please mention it.

Color it with color i then call the recursive function for the next node if it returns true we will return true.

And If it is false then take off the color.

Now if we have tried out every color from 1 to m and it was not possible to color it with any of the m colors then return false.

Code Zone!

Recursion Python Code

Recursion Java Code

Recursion C++ Code

Sb Mai He Kru ...

Khud Bhi Kr le Khuch ..... Nalayk

Time Complexity:O( N^M) (n raised to m)Becouse we try every color on every node
Space Complexity: O(N) + O(N) For using the Extra Space of the Color Array. O(N) for the Recursive Stack Space.