Ninja And Flowers

Moderate
0/80
Average time to solve is 10m
9 upvotes
Asked in companies
SamsungWiproSigmoid

Problem statement

Ninja has ‘N’ gardens labeled from [1, N] under his supervision. He created an array that stores bidirectional paths between I1 and I2, where I1 and I2 are gardens stored at the position I in the array. In each garden, he wants to plant 4 types of flowers.

You need to choose a flower type for each garden such that any two gardens connected by a path, have different types of flowers.

Note: 
1. All gardens have at most three paths coming into or leaving the garden. 
2. There can be more than one possible answer to this question. You need to print the smallest valid answer when all possible answers are sorted in lexicographical order.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains two space-separated integers ‘N’ and ‘X’, denoting the number of gardens Ninja has and the number of queries regarding the paths between the gardens.

The next ‘X’ lines of each test contain an array of ‘X’ pairs where each pair denotes a bidirectional path between the two values of the pair.
Output Format: 
For each test case, you need to return an array of integers denoting the flower type of each garden.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^3
0 <= X <= 10^3
1 <= Y1, Y2 <= N

Time limit: 1 sec
Sample Input 1:
1
4 2
1 2
3 4
Sample Output 1:
1 2 1 2
Explanation of sample input 1:
In the first test case, 
Gardens 1 and 2 have different types, and gardens 3 and 4 have different types. So, a possible answer to the question is when gardens 1 and 3 have the same type and gardens 2 and 4 have the same types of flowers. So print 1 2 1 2
Sample Input 2:
2
3 3
1 2
2 3
3 1
4 3
1 2
2 3
3 4
Sample Output 2:
1 2 3
1 2 1 2
Explanation of sample input 2:
In the first test case, 
Gardens 1 and 2 have different types, gardens 2 and 3 have different types, gardens 3 and 1 have different types. Hence, 1 2 3 is a valid answer. Other valid answers include 1 2 4, 4 2 1, 3 2 1. But 1 2 3 is lexicographically smallest, so you need to print 1 2 3

In the second test case, 
Gardens 1 and 2 have different types, gardens 2 and 3 have different types, gardens 3 and 4 have different types. So print 1 2 1 2.
Hint

Can you think of using greedy algorithms?

Approaches (1)
Using Greedy Algorithm

In this approach, we will use the concept of Graphs and try to convert this problem into the famous colouring problem. We will start by viewing the gardens as a graph, where the path is an edge and the garden is a vertex. As given in the question that there can not be more than 3 connections in the graph, so we can pick a flower that has not yet been taken by any of its adjacent nodes.

 

We will create a graph as an array of pairs of adjacent nodes, then iterate over vertices starting from 0 and assign the first flower that is not yet taken by checking flowers of all adjacent vertices.

 

Algorithm:

  • Create a graph as an array of adjacent nodes
  • Start picking a flower in a greedy manner:
    • Taking flower that is not taken by any of its adjacent vertices
  • Check all connected garden flowers, 0 means that it doesn’t have a flower.
  • Now, all taken flowers are marked, so pick the first untaken flower for the current garden.
  • Return array.
Time Complexity

O(N), where N is the number of gardens.

 

Since we are traversing through each vertex of the graph, the complexity is O(N).

Space Complexity

O(N), where N is the number of gardens.

 

The space required for the graph is O(N), so the overall complexity will be O(N).

Code Solution
(100% EXP penalty)
Ninja And Flowers
Full screen
Console