M - Coloring Problem

Easy
0/40
Average time to solve is 15m
5 upvotes
Asked in companies
UberSamsungSquadstack

Problem statement

You are given an undirected graph with N nodes in the form of an adjacency matrix. You are also given an integer M.

Your task is to find if you can color the vertices of the graph using at most M colors such that no two adjacent vertices are of the same color.

For example:

If the given adjacency matrix is:
[0 1 0]
[1 0 1]
[0 1 0] and M = 3.

The given adjacency matrix tells us that node 1 is connected to node 2 and node 2 is connected to node 3. 

So if we color vertex 1 with ‘red’, vertex 2 with ‘blue’, and vertex 3 with ‘red’, it is possible to color the given graph with two colors which is less than or equal to M.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow.

The first line of the test case contains two space-separated integers N and M, denoting the number of vertices in the undirected graph and the number of colors respectively.

Each of the next N lines of each test case contains N integers denoting a row of the adjacency matrix of the undirected graph.
Output Format: 
For each test case, you need to print a single line containing “Yes” if we can color the given graph with at most M colors. otherwise, print “No”.

The output of each test case will be printed in a separate line.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the given function.
Constraints: 
1 ≤ T ≤ 10
1 ≤ N ≤ 20
1 ≤ M ≤ N

Time Limit: 1 sec.
Sample Input 1:
3
3 3
0 1 0
1 0 1
0 1 0
3 1
0 1 0
1 0 1
0 1 0
2 1
0 1
1 0
Sample Output 1:
Yes
No
No
Explanation of Input 1:
The first test case has already been explained in the example.

The second test case, the given adjacency matrix tells us that node 1 is connected to node 2 and node 2 is connected to node 3. We can see that at least two colors would be needed to color the graph. So it is not possible to color the graph in this case.

The third test case, the given adjacency matrix tells us that node 1 is connected to node 2. We can see that at least two colors would be needed to color the graph. So it is not possible to color the graph in this case.
Sample Input 2:
3
3 3
0 0 0
0 0 1
0 1 0
4 2
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
4 1
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
Sample Output 2
Yes
Yes
No
Hint

Take all different color combinations possible.

Approaches (2)
Naive Approach
  • We will generate all possible combinations of colors possible for coloring the given graph.
  • This can be done recursively by assigning a node each color from 1 to M and doing the same for all nodes.
  • We further check if the adjacent vertices don’t have the same color.
  • If we find such a combination of vertices, we return “Yes”. Otherwise, we return “No”.
Time Complexity

O(M ^ N), where N is the number of vertices in the graph and M is the maximum number of colors allowed. 

 

For each node, there are M possibilities to color it and there are N nodes, which gives us M *.….* M (N times) = M ^ N.

Space Complexity

O(N), where N is the number of vertices in the graph.

 

We are using an array of size N for storing the colors of each vertex, also, in the worst case, we have all the vertices of the graph in the recursion stack. Hence the space complexity is O(N).

Code Solution
(100% EXP penalty)
M - Coloring Problem
Full screen
Console