Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You are given an undirected graph as an adjacency matrix consisting of * 'v'* vertices and an integer

You need to return 'YES' if you can color the graph using at most 'm' colors so that no two adjacent vertices are the same. Else, return 'NO'.

```
Input:
If the given adjacency matrix is:
[0 1 0]
[1 0 1]
[0 1 0] and 'm' = 3.
```

```
Output: YES
Explanation:
The given adjacency matrix tells us that 1 is connected to 2 and 2 is connected to 3. We can use three different colors and color all three nodes.
Hence we return true.
```

Detailed explanation

```
The first line contains two space-separated integers, 'v' and 'm', denoting the number of vertices in the undirected graph and the number of colors, respectively.
Each of the next 'v' lines contains 'v' integers denoting the adjacency matrix of the undirected graph.
```

```
You need to return “YES” if we can color the graph with at most M colors. Otherwise, return “NO”. (without the inverted commas)
```

```
You are not required to print the expected output. It has already been taken care of. Just implement the function.
```

```
3 2
0 1 0
1 0 1
0 1 0
```

```
YES
```

```
The adjacency matrix tells us that 1 is connected to 2, and 2 is connected to 3. We can see that a minimum of 2 colors would be needed to color the graph. So it is possible to color the graph in this case.
```

```
3 1
0 1 0
1 0 1
0 1 0
```

```
NO
```

```
1 ≤ v ≤ 20
1 ≤ m ≤ v
Time Limit: 1 sec
```