Color Value of Graph

Hard
0/120
profile
Contributed by
1 upvote
Asked in companies
AppleHCL INFOSYSTEMAccolite

Problem statement

You are given a directed graph, with ‘N’ nodes and each node labelled from 0 to ‘N - 1’. You are also given a ‘colour’ array, where ‘colour [i]’ represents the colour of ‘ith’ node. The Colour value of a path is the frequency of the most frequently occurring colour in the path. Your task is to find the maximum colour value of all the valid paths in the graph, or return -1 if there exists a cycle.

Note: 
The graph is connected.
For example: 
You are given the following graph:

altText

Here the path 0->1->2 has the colour value of 3, which is the maximum colour value of the graph. Hence the answer is 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains ‘T’ representing the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘M’ representing the number of nodes and edges.

The next ‘M’ lines of the input contain two space-separated integers ‘a’ and ‘b’ representing a directed edge from ‘a’ to ‘b’.

The following line contains a string of ‘N’ characters, where ith character represents the colour of ‘ith’ node.
Output Format: 
For each test case, print a single integer representing the largest colour value of the graph.

Print a separate line for each test case.
Constraints: 
1 <= N, M <= 10^5
0 <= a, b < N

‘colour’ array contains lower case english alphabet characters.
Time Limit: 1 sec.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
2
6 5
0 1
1 2
3 1
3 5
4 3
aaabcd
7 6
0 1
1 2
2 6
3 1
3 5
4 3
abacbdb
Sample Output 1:
3
3
Explanation:
For the first test case, you are given the following graph:

altText

Here the path 0->1->2 has the colour value of 3, which is the maximum colour value of the graph. Hence the answer is 3.

For the second test case, you are given the following graph:

altText

Here the path 4->3->1->2->6, has the colour value of 3, which is the maximum colour value of the graph. Hence the answer is 3.
Sample Input 2
2
1 1
0 0
a
2 1
0 1
ab
Sample Output 2
-1
1
Hint

Process all nodes in topological order.

Approaches (2)
Topological Sort BFS

In this approach, we will visit the nodes in topological order, as in a topological order every node that can lead up to a current node in a graph, will already be processed. Therefore we will do a normal top sort, but for each node, we will maintain a colour frequency which will represent the maximum frequency of every colour leading up to the current node. Then we will update the colour frequency of every neighbour of the current node.

 

Algorithm:

  • Create a 2D matrix called ‘adjList’.
  • Create an empty array ‘indegree’, of size equal to the length of the string ‘colours’, with all values initialised as 0.
  • Iterate edge through edges
    • Insert edge[1] in adjList[edge[0]].
    • Increase indegree[edge[1]] by 1
  • Create an array of integer arrays of length 26 called ‘colourCounts’.
  • Initialize an empty queue ‘q’.
  • Iterate node from 0 to length of adjList - 1
    • If indegree[node] is 0, then insert the node in q
  • Set res as 0
  • Set processed as 0
  • While q is not empty
    • Iterate loop as many times as the length of ‘q’
      • Set node as the last element of  ‘q’ and pop the ‘q’.
      • Set currentColour as the index of character at colours[node]
      • Increased processed by 1
      • Set res as maximum of itself and coloursCount[node][currentColour].
      • Iterate child through adjList[node]
        • Iterate colour from 0 to 25
          • Set colourCount[child][colour] as maximum of itself coloutCount[node][colour]
        • Decrease indegree[child] by 1
        • If indegree[child] is 0, insert child in ‘q’.
  • If processed is equal to the length of colours return res otherwise return -1.
Time Complexity

O(N + M), Where N and M are the number of nodes and the number of edges in the graph.
 

We are performing a Breadth-first search to find the topological sort which costs O(N + M) time. Hence the final time complexity is O(N + M).

Space Complexity

O(N), Where N is the number of nodes in the graph.

 

The adjacency list, colour frequency map and then indegree list all will take O(N) space. Hence the final space complexity is O(N)

Code Solution
(100% EXP penalty)
Color Value of Graph
Full screen
Console