Ninja And Flowers

Posted: 26 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
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 
Approach 1

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.
Try Problem