Last Updated: 4 Dec, 2021

Color Value of Graph

Hard

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In this approach, we will visit the nodes in topological sort, but here we will go toward the leaf of the graph and then go back and update the current node’s colour frequencies from their child’s colour frequencies.

We will create a dfs(node, colours, adjList, coloursCount, visited), where node is the current visiting node, colours is the string representing the colours of nodes, coloursCount is the map of frequencies and visited is the visited node array.

Algorithm:

In the dfs(node, colours, adjList, coloursCount, visited):
- If visited[node] is 0
  - Set visited[node] as 1
  - Iterate child through adjList[node]
    - If dfs(child, colours, adjList, coloursCount, visited) is infinity, return infinity
    - Iterate colour from 0 to 25
      - Set colourCount[node][colour] as maximum of itself and colourCount[child][colour]
    - Set currentColour as the index of character at colors[node]
    - Increase colourCount[node][currentColour] by 1
    - Set visited[node] as 2
- Return coloursCount[node][currentColour] if visited[node] equal to 2 otherwise return MAX

In the given function
- Create a 2D matrix called ‘adjList’ and create an empty array of 0’s of size colours, called ‘visited’.
- Iterate edge through edges
  - Insert edge[1] in adjList[edge[0]].
- Create an array of integer arrays of length 26 called ‘colourCounts’.
- Set res as 0
- Iterate node from 0 to length of adjList - 1
  - Set res as the maximum of itself and dfs(node, colours, adjList, colourCount, visited)
  - If res is equal to infinity
    - Return -1
- Return res

Solve now