M-Coloring Problem #Graph #Backtracking #MUST DO #AMAZON

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)}
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
Your Task:
Your task is to complete the function graphColoring() which takes the 2d-array graph[], the number of colours and the number of nodes as inputs and returns true if answer exists otherwise false. 1 is printed if the returned value is true, 0 otherwise. The printing is done by the driver's code.
Note: In the given 2d-array graph[], if there is an edge between vertex X and vertex Y graph[] will contain 1 at graph[X-1][Y-1], else 0. In 2d-array graph[ ], nodes are 0-based indexed, i.e. from 0 to N-1.

Expected Time Complexity: O(MN).
Expected Auxiliary Space: O(N).

[varshi]

That's a great explanation, You nailed it I say. I watched 4 to 5 videos, But your's is best!!!

[sonusah]

This solution by you for this problem is better than any other solution for this problem on YT, even better than Striver

[HARSHITSINGH-jfff]

Ur dedication showing that you are explanation

[siddharthupadhyay]

After going through so many videos, I found this one very helpful.

[pawanlok]

thank a lot for using small concepts to solve this problem

[sagarsharma-bpwe]

Thanks a lot, Everybody has given it's wrong approach

[darnavik]

17:57 you disturbed your peacefully sleeping friend at the back 😅

[poojarenake]

Thanks for the video. Now properly understood..

[harsh]

This is exactly what I was looking for!!
Thx a lot 🔥

[shashanksingh]

why do we assign -1? Won't the value be updated in the next iteration itself?

[pointsoflife]

Will u meet me and than a create a channel

[rajaptdr]

I am not able to understanding why we need to assign -1 back to the color index, can we just skip this?

[rahulpoddar]

Aapka name Alisha hai... maine bachpan mein sunna tha ki pariyo🧚ka name nhi hota hai... 😅
Wase Aapka smile bahut pyara 💘hai ...
Mujhe question samjh mein aagya pura acha lga sikhne mein ✨...
M colouring problem done 👍
Thanks ❤️
Aur aap bhi bahut pyari hai ...❤️

[mohitgupta]

java solution

class solve {
// Function to determine if graph can be coloured with at most M colours

public boolean isSafe(boolean graph[][], int color[], int m, int n, int i, int j){

for(int k=0;k<n;k++){
if(graph[i][k]==true && color[k]==j){
return false;
}
}
return true;
}
public boolean helper(boolean graph[][], int color[], int m, int n, int i){
if(i==n){
return true;
}

//coloring to graph [having m colors atmost]
for(int j=1;j<=m;j++){
if(isSafe(graph, color, m, n, i, j)){ // is it safe to give j color to ith node
color[i]=j;
if(helper(graph, color, m, n, i+1)){
return true;
}
color[i]=-1;
}
}

return false;
}
public boolean graphColoring(boolean graph[][], int m, int n) {
// Your code here
int color[]=new int[n];

return helper(graph, color, m, n, 0); // current i at 0th node
}