Login

Striver SDE Sheet Problems

Problem title

Difficulty

Avg time to solve

Find Four Elements That Sums To A Given Value

Moderate

10 mins

M-Coloring Problem

Moderate

15 mins

Word Break II

Hard

15 mins

Implement Atoi Function

Easy

10 mins

Tree Traversals

Easy

15 mins

Topological Sort

Moderate

30 mins

Matrix Chain Multiplication

Moderate

40 mins

Rotate Matrix

Easy

15 mins

Cut Logs

Hard

50 mins

Set Matrix Ones

Easy

15 mins

Problem

Submissions

9

Avg. time to solve

15 min

Success Rate

85%

Problem Statement

```
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 1 is connected to 2 and 2 is connected to 3. So if we color vertex 1 with 2, vertex 2 with 1, and vertex 3 with 2, it is possible to color the given graph with 2 colors: M.
```

```
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 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.
```

```
For each test case, you need to return “YES” if we can color the given 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.
```

```
1 ≤ T ≤ 1000
1 ≤ V ≤ 20
1 ≤ M ≤ V
Time Limit : 1 sec
```

```
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
```

```
YES
NO
NO
```

```
The first test case has already been explained in the example.
In the second test case, the given adjacency matrix tells us that 1 is connected to 2 and 2 is connected to 3. We can see that minimum of 2 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 1 is connected to 2. We can see that minimum 2 colors would be needed to color the graph. So it is not possible to color the graph in this case.
```

```
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
```

```
YES
YES
NO
```

Console

Sample Test Case

Custom Test Case

Download Test Cases

Test Case 1

Test Case 2

Test Case 3

Saving Code...

Full Screen Mode

Change Language

Change Theme

Solution submission not allowed

Save Code

Reset Code