[Solved] Basketball Players Contest Problem

Basketball Players: There are ‘N’ basketball players, where ‘ith’ players have height ‘H[i]’. There is an array of pairs’ A’ where a pair (‘X’, ‘Y’) (where ‘X’ and ‘Y’ are not the same) denotes that player ‘X’ has won against ‘Y’ in a match.

Let’s define a sequence of winnings as ‘S[1]’, ‘S[2]’,…, ‘S[k]’, where each element denotes a player. In the sequence for all j (1 <= j < k) ‘S[j]’ has won a match against ‘S[j+1]’, if this condition is not followed the sequence is not called sequence of winnings.

Let’s define sequence value as the maximum number of players with the same height in a winning sequence.

You have to determine the maximum possible sequence value. If any sequence starts and ends with the same player, print -1. Else, print the sequence value.

Example :

'N' = 5, 'M' = 4, 'H' = {1, 2, 1, 2, 3}, 'A' = { {1, 2}, {2, 3}, {4, 5}, {5, 3} }.

Sequences of length 1 : { {1}, {2}, {3}, {4}, {5} }. Sequence value = 1 as all the sequences have exactly one player with the same height.

Sequences of length 2 : { {1, 2}, {2, 3}, {4, 5}, {5, 3} }. Sequence value = 1 as all the sequences have at most 1 player with the same height.

Sequences of length 3 : { {1, 2, 3}, {4, 5, 3} }. Sequence value = 2 as the sequence {1, 2, 3} has two players 1 and 2 with the same height.

There are no sequences of length > 3.

So, we will print 2.

Basketball Players Contest Problem

Input Format :

The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers, 'N' and 'M', denoting the number of players and the number of pairs, respectively.

The next line contains 'N' space-separated integers representing the height of players.

The next 'M' lines contain pairs. Each line consists of two integers, 'X' and 'Y'.

Output Format :

For each test case, print the maximum possible sequence value or print -1 if there is any sequence that starts and ends at the same player.

Print the output of each test case in a new 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
2 <= N <= 10^5
1 <= M <= min((N*(N-1))/2, 10^5)
1 <= X, Y <= N, X != Y
1 <= 'H[i]' <= 10

The Sum of 'N' over all test cases is <= 10^5.
The Sum of 'M' over all test cases is <= 10^5.

Time Limit: 1 sec

Sample Input 1 :

2
3 3
1 1 1
1 2
2 3
1 3
3 4
1 1 1
1 2
2 3
1 3
3 1

Sample Output 1 :

3
-1

Explanation Of Sample Input 1 :

For test case 1:

Sequences of length 1 : { {1}, {2}, {3} }. Sequence value = 1 as all the sequences have exactly one player with the same height.

Sequences of length 2 : { {1, 2}, {2, 3}, {1, 3} }. Sequence value = 2 as all the sequences have exactly 2 players with the same height.

Sequences of length 3 : { {1, 2, 3} }. Sequence value = 3 as the sequence has 3 players with the same height.

For test case 2:

The sequence {1, 3, 1} starts at 1 and ends at 1.

Sample Input 2 :

2
5 7
1 2 1 4 1
1 2
1 3
1 4
2 3
2 5
3 4
4 5
4 4
3 4 2 1
1 2
2 3
3 4
4 1

Sample Output 2 :

3
-1

Solution

Brute Force

Approach : 

• Let’s denote every player as a vertex and every pair (‘X’, ‘Y’) as a directed edge from ‘X’ to ‘Y’ in a graph.
• Any sequence which starts and ends at one player denotes a cycle in this graph.
• We will check if there is a cycle in this graph. If there is, we will print -1.
• If there is no cycle, we will start a dfs from every node of the graph, traverse along the path, and keep the heights count, traverse, and traverse. Also, we will keep updating the maximum sequence value.

Algorithm:
 

• Create an adjacency list ‘ADJ’ using the pairs of ‘A’ as directed edges.
• If there is any cycle in the graph, return -1.
• Initialize a variable ‘MAX_SEQ_VAL’ with 0.
• Loop through all the players from ‘i’ = 1 to ‘i’ = ‘N’ :
  • Run a dfs from ‘i’ and keep a count of heights along the path, keep and keep updating the ‘MAX_SEQ_VAL’.
• Return ‘MAX_SEQ_VAL’.

Time Complexity

O(N * M), where ‘N’ is the number of players, and ‘M’ is the number of pairs.

First, we are checking if there is any cycle in the graph which takes O(N + M). We are running a dfs starting as a source from every player. Each dfs may take O(M) time in the worst case. So the total Time Complexity is O(N * M).

Space Complexity

O(N + M), where ‘N’ is the number of players, and ‘M’ is the number of pairs.

We are creating an adjacency list that takes O(M) space and using O(N) space while detecting the cycle. So, the total Space Complexity is O(N + M).

/*
    Time complexity: O(N * M)
    Space complexity: O(N + M)

    where 'N' is the number of players, and 'M' is the number of pairs.
*/

#define WHITE 0
#define GREY 1
#define BLACK 2
#define MAX_HEIGHT 10

// Helper function of isCycleExist().
bool isCycleExistUtil(vector<vector<int>> &adj, vector<int> &color, int cur) {

	// Vertex is now under process.
	color[cur] = GREY;

	// Loop through all the adjcent vertex of 'cur'.
	for (auto &nxt : adj[cur]) {
		// Found Back Edge.
		if (color[nxt] == GREY) {
			return true;
		}
		// If cycle is found ahead.
		if (color[nxt] == WHITE && isCycleExistUtil(adj, color, nxt)) {
			return true;
		}
	}

	// Vertex is processed.
	color[cur] = BLACK;

	// No cycle found from here.
	return false;
}

// Function to check if cycle exists in a graph corresponding to 'adj'.
bool isCycleExist(vector<vector<int>> &adj, int numVertices) {

	/*
	Create an array to store the color of each vertex.
	WHITE -> Vertex is not processed.
	GREY -> Vertex is in process.
	BLACK -> Vertex is processed.
	*/
	vector<int> color(numVertices + 1, WHITE);

	// Loop through all the vertices.
	for (int cur = 1; cur <= numVertices; ++cur) {
		// If the current vertex is not processed, process it.
		if (color[cur] == WHITE && isCycleExistUtil(adj, color, cur)) {
			// Cycle exits.
			return true;
		}
	}

	// No cycle exists.
	return false;
}

// Function to perform a dfs and update 'maxSeqVal'.
void dfs(vector<vector<int>> &adj, vector<int> &height, vector<int> &heightsCnt, int &maxSeqVal, int cur) {
	// Increment the count of height by 1.
	heightsCnt[height[cur - 1]]++;

	// Store the maximum sequence value till here.
	int maxSeqValHere = 0;

	// Loop through all the heights and update 'maxSeqValHere'.
	for (int h = 1; h <= MAX_HEIGHT; ++h) {
		maxSeqValHere = max(maxSeqValHere, heightsCnt[h]);
	}

	// Update maximum sequence value.
	maxSeqVal = max(maxSeqValHere, maxSeqVal);

	// Loop through all the adjacent vertices of 'cur'.
	for (auto &nxt : adj[cur]) {
		// Perform a dfs from 'nxt'.
		dfs(adj, height, heightsCnt, maxSeqVal, nxt);
	}

	// Backtrack the count of height.
	heightsCnt[height[cur - 1]]--;
}

int maxSequenceVal(vector<int> &h, vector<pair<int, int>> &a, int n, int m) {
	// Create an adjacency list to store edges.
	vector<vector<int>> adj(n + 1);

	// Loop through all the directed edges
	for (auto &x : a) {
		// Directed edge from 'x.first' to 'x.second'
		int from = x.first, to = x.second;
		adj[from].push_back(to);
	}

	// Check if cycle exists
	if (isCycleExist(adj, n)) {
		// Cycle exists.
		return -1;
	}

	// Initialise the sequence value with 0.
	int maxSeqVal = 0;

	for (int i = 1; i <= n; ++i) {
		vector<int> heightsCnt(MAX_HEIGHT + 1, 0);
		// Run a dfs to update the maximum sequence value of a path starting from vertex 'i'.
		dfs(adj, h, heightsCnt, maxSeqVal, i);
	}

	// Return the maximum sequence value.
	return maxSeqVal;
}

/*
    Time complexity: O(N * M)
    Space complexity: O(N + M)

    where 'N' is the number of players, and 'M' is the number of pairs.
*/

import java.util.Vector;

public class Solution {

    static int MAX_HEIGHT = 10;
    static int WHITE = 0, BLACK = 1, GREY = 2;
    static int max_seq_val = 0;

    static int maxSequenceVal(int h[], int a[][], int n, int m) {
        // Create an adjacency list to store edges.
        Vector < Vector < Integer >> adj = new Vector < > (n + 1);
        for (int i = 0; i < n + 1; i++) {
            adj.add(new Vector < > ());
        }

        // Loop through all the directed edges
        for (int i = 0; i < a.length; i++) {
            // Directed edge from 'x.first' to 'x.second'
            int from = a[i][0], to = a[i][1];
            adj.get(from).add(to);
        }

        // Check if cycle exists
        if (is_cycle_exists(adj, n)) {
            // Cycle exists.
            return -1;
        }

        // Initialise the sequence value with 0.
        max_seq_val = 0;

        for (int i = 1; i <= n; ++i) {
            int heights_cnt[] = new int[MAX_HEIGHT + 1];
            // Run a dfs to update the maximum sequence value of a path starting from vertex 'i'.
            dfs(adj, h, heights_cnt, i);
        }

        // Return the maximum sequence value.
        return max_seq_val;
    }

    // Function to perform a dfs and update 'max_seq_val'.
    static void dfs(Vector < Vector < Integer >> adj, int height[], int heights_cnt[], int cur) {
        // Increment the count of height by 1.
        heights_cnt[height[cur - 1]]++;

        // Store the maximum sequence value till here.
        int max_seq_val_here = 0;

        // Loop through all the heights and update 'max_seq_val_here'.
        for (int h = 1; h <= MAX_HEIGHT; ++h) {
            max_seq_val_here = Math.max(max_seq_val_here, heights_cnt[h]);
        }

        // Update maximum sequence value.
        max_seq_val = Math.max(max_seq_val_here, max_seq_val);

        // Loop through all the adjacent vertices of 'cur'.
        for (int nxt: adj.get(cur)) {
            // Perform a dfs from 'nxt'.
            dfs(adj, height, heights_cnt, nxt);
        }

        // Backtrack the count of height.
        heights_cnt[height[cur - 1]]--;
    }

    // Function to check if cycle exists in a graph corresponding to 'adj'.
    static boolean is_cycle_exists(Vector < Vector < Integer >> adj, int num_vertices) {
    /*
    Create an array to store the color of each vertex.
    WHITE -> Vertex is not processed.
    GREY -> Vertex is in process.
    BLACK -> Vertex is processed.
    */
        // Initially all vertices are coloured 'WHITE'.
        int color[] = new int[num_vertices + 1];

        // Loop through all the vertices.
        for (int cur = 1; cur <= num_vertices; ++cur) {
            // If the current vertex is not processed, process it.
            if (color[cur] == WHITE && is_cycle_exists_util(adj, color, cur)) {
                // Cycle exits.
                return true;
            }
        }

        // No cycle exists.
        return false;
    }

    // Helper function of is_cycle_exists().
    static boolean is_cycle_exists_util(Vector < Vector < Integer >> adj, int color[], int cur) {

        // Vertex is now under process.
        color[cur] = GREY;

        // Loop through all the adjcent vertex of 'cur'.
        for (int nxt: adj.get(cur)) {
            // Found Back Edge.
            if (color[nxt] == GREY) {
                return true;
            }
            // If cycle is found ahead.
            if (color[nxt] == WHITE && is_cycle_exists_util(adj, color, nxt)) {
                return true;
            }
        }

        // Vertex is processed.
        color[cur] = BLACK;

        // No cycle found from here.
        return false;
    }

}

'''
	Time complexity: O(N * M)
	Space complexity: O(N + M)

	where 'N' is the number of players, and 'M' is the number of pairs.
'''

WHITE = 0
GREY = 1
BLACK = 2
MAX_HEIGHT = 10

from typing import *

# Helper function of is_cycle_exists().
def is_cycle_exists_util(adj, color, cur) :

	# Vertex is now under process.
	color[cur] = GREY

	# Loop through all the adjcent vertex of 'cur'.
	for nxt in adj[cur] :
		# Found Back Edge.
		if(color[nxt] == GREY) :
			return True
		
		# If cycle is found ahead.
		if(color[nxt] == WHITE and is_cycle_exists_util(adj, color, nxt)) :
			return True
		
	

	# Vertex is processed.
	color[cur] = BLACK

	# No cycle found from here.
	return False


# Function to check if cycle exists in a graph corresponding to 'adj'.
def is_cycle_exists(adj, num_vertices) :

	'''
		Create an array to store the color of each vertex.
		WHITE -> Vertex is not processed.
		GREY -> Vertex is in process.
		BLACK -> Vertex is processed.
	'''
	color = [WHITE] * (num_vertices + 1)

	# Loop through all the vertices.
	for cur in range(1, num_vertices + 1):
		# If the current vertex is not processed, process it.
		if(color[cur] == WHITE and is_cycle_exists_util(adj, color, cur)) :
			# Cycle exits.
			return True
		
	# No cycle exists.
	return False


# Function to perform a dfs and update 'max_seq_val'.
def dfs(adj, height, heights_cnt, max_seq_val, cur) :
	# Increment the count of height by 1.
	heights_cnt[height[cur - 1]] += 1

	# Store the maximum sequence value till here.
	max_seq_val_here = 0

	# Loop through all the heights and update 'max_seq_val_here'.
	for h in range(1, MAX_HEIGHT + 1) :
		max_seq_val_here = max(max_seq_val_here, heights_cnt[h])
	

	# Update maximum sequence value.
	max_seq_val[0] = max(max_seq_val_here, max_seq_val[0])

	# Loop through all the adjacent vertices of 'cur'.
	for nxt in adj[cur]:
		# Perform a dfs from 'nxt'.
		dfs(adj, height, heights_cnt, max_seq_val, nxt)
	

	# Backtrack the count of height.
	heights_cnt[height[cur - 1]] -= 1


def maxSequenceVal(h: List[int], a: List[List[int]], n: int, m: int) -> int:
	# Create an adjacency list to store edges.
	adj = [[] for i in range(n + 1)]

	# Loop through all the directed edges
	for x in a:
		# Directed edge from 'x[0]' to 'x[1]'
		from_ = x[0]
		to = x[1]
		adj[from_].append(to)
	

	# Check if cycle exists
	if(is_cycle_exists(adj, n)) :
		# Cycle exists.
		return -1
	

	# Initialise the sequence value with 0.
	max_seq_val = [0]

	for i in range(1, n + 1) :
		heights_cnt = [0]  * (MAX_HEIGHT + 1)
		# Run a dfs to update the maximum sequence value of a path starting from vertex 'i'.
		dfs(adj, h, heights_cnt, max_seq_val, i)
	

	# Return the maximum sequence value.
	return max_seq_val[0]

Optimal

Approach :

• We will solve this problem using dynamic programming and the idea of topological sort.
• If there is any cycle in the graph, we will print -1.
• Let us assume that the graph is a directed acyclic (DAG). Now, it is always better to start a sequence with a vertex having zero number of incoming edges. (At least one such vertex always exists in a DAG).
• We will use a 2-d array ‘dp[i][j]’, where ‘dp[i][j]’ denotes the maximum count of players with height ‘j’ and the sequence is starting from player ‘i’.
• We will add all the vertices having zero number of incoming edges in a queue.
• Now we will keep popping from the queue, and for every vertex, we will remove all the outgoing edges from it.
• If any of its adjacent vertices now have zero number of incoming edges, we will add this vertex to the queue.
• We will keep updating ‘dp’ for adjacent nodes using the current node.

Algorithm:

• Create an adjacency list ‘ADJ’ using the pairs of ‘A’ as directed edges.
• Create an array ‘IN_DEGREE’ of length ‘N’ and fill it with the number of incoming edges using the pairs of ‘A’ as directed edges.
• Create a 2-d array ‘DP’ of size ‘N’ * ‘MAX_HEIGHT’ initialized with 0.
• Create an empty queue ‘VERTICES_QUEUE’.
• Loop through all the vertices from ‘i’ = 1 to ‘i’ = ‘N’ :
  • If ‘IN_DEG[i]’ == 0 :
    • Push ‘i’ into ‘VERTICES_QUEUE’;
    • Increment ‘DP[ i ][ H[i] ]’ by 1.
• Initialize a variable ‘NUM_VERTICES_PROCESSED’ with 0.
• Run a loop while ‘VERTICES_QUEUE’ is non-empty :
  • Initialize ‘CUR_VERTEX’ with the vertex at the front of ‘VERTICES_QUEUE’.
  • Pop the front vertex from ‘VERTICES_QUEUE’.
  • Increment ‘NUM_VERTICES_PROCESSED’ by 1.
  • Loop through all the adjacent vertices of ‘CUR_VERTEX’ :
    • Let ‘NEXT_VERTEX’ be the adjacent vertex.
    • Loop through all the heights from ‘j’ = 1 to ‘j’ = MAX_HEIGHT :
      • ‘DP[NEXT_VERTEX][j]’ = max( ‘DP[NEXT_VERTEX][j]’ , ‘DP[CUR_VERTEX][j]’ ).
    • Decrement ‘IN_DEGREE[NEXT_VERTEX]’ by 1.
    • If ‘IN_DEGREE[NEXT_VERTEX]’ == 0 :
      • Push ‘NEXT_VERTEX’ into ‘VERTICES_QUEUE’.
      • Increment ‘DP[ NEXT_VERTEX ][ H[NEXT_VERTEX] ]’ by 1.
• If ‘NUM_VERTICES_PROCESSED’ is less than the total number of vertices, return -1.
• Initialize a variable ‘MAX_SEQ_VAL’ with the maximum value of ‘DP’.
• Return ‘MAX_SEQ_VAL’.

Time Complexity

O( (N + M ) * MAX_HEIGHT ), where ‘N’ is the number of players, ‘MAX_HEIGHT’ is the maximum possible player height, and ‘M’ is the number of pairs.
 

Initializing ‘DP’ and taking the maximum value from ‘DP’ takes O(N * MAX_HEIGHT). Initialising the queue takes O(N) time. Every vertex gets pushed into and popped from the queue at most once, so it takes O( (N + M) * MAX_HEIGHT ). So, the total Time Complexity is O( (N + M) * MAX_HEIGHT ).

Space Complexity

O(N * MAX_HEIGHT + M), where ‘N’ is the number of players, ‘MAX_HEIGHT’ is the maximum possible player height, and ‘M’ is the number of pairs.

Since ‘ADJ’ takes O(M) space and the 2-d array ‘DP’ takes O(N * MAX_HEIGHT) time. So, the Time Complexity is O(N * MAX_HEIGHT + M).

/*
    Time complexity: O(N * M)
    Space complexity: O(N + M)

    where 'N' is the number of players, and 'M' is the number of pairs.
*/

#define WHITE 0
#define GREY 1
#define BLACK 2
#define MAX_HEIGHT 10

// Helper function of isCycleExist().
bool isCycleExistUtil(vector<vector<int>> &adj, vector<int> &color, int cur) {

	// Vertex is now under process.
	color[cur] = GREY;

	// Loop through all the adjcent vertex of 'cur'.
	for (auto &nxt : adj[cur]) {
		// Found Back Edge.
		if (color[nxt] == GREY) {
			return true;
		}
		// If cycle is found ahead.
		if (color[nxt] == WHITE && isCycleExistUtil(adj, color, nxt)) {
			return true;
		}
	}

	// Vertex is processed.
	color[cur] = BLACK;

	// No cycle found from here.
	return false;
}

// Function to check if cycle exists in a graph corresponding to 'adj'.
bool isCycleExist(vector<vector<int>> &adj, int numVertices) {

	/*
	Create an array to store the color of each vertex.
	WHITE -> Vertex is not processed.
	GREY -> Vertex is in process.
	BLACK -> Vertex is processed.
	*/
	vector<int> color(numVertices + 1, WHITE);

	// Loop through all the vertices.
	for (int cur = 1; cur <= numVertices; ++cur) {
		// If the current vertex is not processed, process it.
		if (color[cur] == WHITE && isCycleExistUtil(adj, color, cur)) {
			// Cycle exits.
			return true;
		}
	}

	// No cycle exists.
	return false;
}

// Function to perform a dfs and update 'maxSeqVal'.
void dfs(vector<vector<int>> &adj, vector<int> &height, vector<int> &heightsCnt, int &maxSeqVal, int cur) {
	// Increment the count of height by 1.
	heightsCnt[height[cur - 1]]++;

	// Store the maximum sequence value till here.
	int maxSeqValHere = 0;

	// Loop through all the heights and update 'maxSeqValHere'.
	for (int h = 1; h <= MAX_HEIGHT; ++h) {
		maxSeqValHere = max(maxSeqValHere, heightsCnt[h]);
	}

	// Update maximum sequence value.
	maxSeqVal = max(maxSeqValHere, maxSeqVal);

	// Loop through all the adjacent vertices of 'cur'.
	for (auto &nxt : adj[cur]) {
		// Perform a dfs from 'nxt'.
		dfs(adj, height, heightsCnt, maxSeqVal, nxt);
	}

	// Backtrack the count of height.
	heightsCnt[height[cur - 1]]--;
}

int maxSequenceVal(vector<int> &h, vector<pair<int, int>> &a, int n, int m) {
	// Create an adjacency list to store edges.
	vector<vector<int>> adj(n + 1);

	// Loop through all the directed edges
	for (auto &x : a) {
		// Directed edge from 'x.first' to 'x.second'
		int from = x.first, to = x.second;
		adj[from].push_back(to);
	}

	// Check if cycle exists
	if (isCycleExist(adj, n)) {
		// Cycle exists.
		return -1;
	}

	// Initialise the sequence value with 0.
	int maxSeqVal = 0;

	for (int i = 1; i <= n; ++i) {
		vector<int> heightsCnt(MAX_HEIGHT + 1, 0);
		// Run a dfs to update the maximum sequence value of a path starting from vertex 'i'.
		dfs(adj, h, heightsCnt, maxSeqVal, i);
	}

	// Return the maximum sequence value.
	return maxSeqVal;
}

/*
    Time complexity: O((N + M) * MAX_HEIGHT)
    Space complexity: O(N * MAX_HEIGHT + M)

    where 'N' is the number of players, and 'M' is the number of pairs.
*/

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Vector;

public class Solution {

    static int MAX_HEIGHT = 10;

    static int maxSequenceVal(int h[], int a[][], int n, int m) {
        // Create an adjacency list to store edges.
        Vector < Vector < Integer >> adj = new Vector < > (n + 1);
        for (int i = 0; i < n + 1; i++) {
            adj.add(new Vector < > ());
        }

        // Store the number of incoming edges of each vertex.
        int in_degree[] = new int[n + 1];

        // dp[i][j] = maximum count of players with height 'j' and the sequence is ending at vertex 'i'.
        int dp[][] = new int[n + 1][MAX_HEIGHT + 1];

        // Loop through all the directed edges
        for (int i = 0; i < a.length; i++) {
            // Directed edge from 'x.first' to 'x.second'
            int from = a[i][0], to = a[i][1];
            adj.get(from).add(to);
            in_degree[to]++;
        }

        // Create an empty queue for processing vertices.
        Queue < Integer > vertices_queue = new ArrayDeque < > ();

        // Loop through all the vertices.
        for (int i = 1; i <= n; ++i) {
            // If 'in_degree[i] = 0', it is always better to start the path from here.
            if (in_degree[i] == 0) {
                // Push vertex 'i' into the queue.
                vertices_queue.add(i);
                // Path ending at vertex 'i' has one more vertex of height 'h[i]' which is 'i' itself.
                dp[i][h[i - 1]]++;
            }
        }

        // Count the number of vertices processed in the queue.
        int num_vertices_processed = 0;

        // Run until queue is non-empty.
        while (!vertices_queue.isEmpty()) {
            // Fetch the vertex at the front of the queue.
            int cur_vertex = vertices_queue.poll();

            // Increment number of processed vertices by 1.
            num_vertices_processed++;

            // Loop through all the adjacent vertices of 'cur_vertex'.
            for (int next_vertex: adj.get(cur_vertex)) {
                // Update the values of 'dp' for paths ending at 'next_vertex'.
                for (int j = 1; j <= MAX_HEIGHT; ++j) {
                    dp[next_vertex][j] = Math.max(dp[next_vertex][j], dp[cur_vertex][j]);
                }

                // Remove this edge from 'cur_vertex' to 'next_vertex'.
                in_degree[next_vertex]--;

                // If there are zero number of incoming edges of 'next_vertex', push it into queue.
                if (in_degree[next_vertex] == 0) {
                    vertices_queue.add(next_vertex);
                    // Path ending at vertex 'next_vertex' has one more vertex of height 'h[next_vertex - 1]' which is 'next_vertex' itself.
                    dp[next_vertex][h[next_vertex - 1]]++;
                }
            }
        }

        // If number of processed vertices < total number of vertices, there must be a cycle in the graph.
        if (num_vertices_processed < n) {
            return -1;
        }

        // Initialise the sequence value with 0.
        int max_seq_val = 0;

        // Finding the maximum value of 'max_seq_val'.
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= MAX_HEIGHT; ++j) {
                max_seq_val = Math.max(max_seq_val, dp[i][j]);
            }
        }

        // Return the maximum sequence value.
        return max_seq_val;
    }
}

'''
	Time complexity: O((N + M) * MAX_HEIGHT)
	Space complexity: O(N * MAX_HEIGHT + M)

	where 'N' is the number of players, and 'M' is the number of pairs.
'''

from typing import *

def maxSequenceVal(h: List[int], a: List[List[int]], n: int, m: int) -> int:
	MAX_HEIGHT = 10
	# Create an adjacency list to store edges.
	adj = [[] for i in range(n + 1)]

	# Store the number of incoming edges of each vertex.
	in_degree = [0] * (n + 1)

	# dp[i][j] = maximum count of players with height 'j' and the sequence is ending at vertex 'i'.
	dp = [[0 for j in range(MAX_HEIGHT + 1)] for i in range(n + 1)]

	# Loop through all the directed edges
	for x in a :
		# Directed edge from 'x[0]' to 'x[1]'
		from_ = x[0]
		to = x[1]
		adj[from_].append(to)
		in_degree[to] += 1
	

	# Create an empty queue for processing vertices.
	vertices_queue = []

	# Loop through all the vertices.
	for i in range(1, n + 1):
		# If 'in_degree[i] = 0', it is always better to start the path from here.
		if(not in_degree[i]) :
			# Push vertex 'i' into the queue.
			vertices_queue.append(i)
			# Path ending at vertex 'i' has one more vertex of height 'h[i]' which is 'i' itself.
			dp[i][h[i - 1]] += 1
		
	

	# Count the number of vertices processed in the queue.
	num_vertices_processed = 0

	# Run until queue is non-empty.
	while(len(vertices_queue)) :
		# Fetch the vertex at the front of the queue.
		cur_vertex = vertices_queue[0]
		# Pop this vertex from the queue.
		vertices_queue.pop(0)

		# Increment number of processed vertices by 1.
		num_vertices_processed += 1

		# Loop through all the adjacent vertices of 'cur_vertex'.
		for next_vertex in adj[cur_vertex]:
			# Update the values of 'dp' for paths ending at 'next_vertex'.
			for j in range(1, MAX_HEIGHT + 1) :
				dp[next_vertex][j] = max(dp[next_vertex][j], dp[cur_vertex][j])
			
			
			# Remove this edge from 'cur_vertex' to 'next_vertex'.
			in_degree[next_vertex] -= 1

			# If there are zero number of incoming edges of 'next_vertex', push it into queue.
			if(not in_degree[next_vertex]) :
				vertices_queue.append(next_vertex)
				# Path ending at vertex 'next_vertex' has one more vertex of height 'h[next_vertex - 1]' which is 'next_vertex' itself.
				dp[next_vertex][h[next_vertex - 1]] += 1
			
		
	

	# If number of processed vertices < total number of vertices, there must be a cycle in the graph.
	if(num_vertices_processed < n) :
		return -1
	

	# Initialise the sequence value with 0.
	max_seq_val = 0

	# Finding the maximum value of 'max_seq_val'.
	for  i in range(1, n + 1):
		for j in range(1, MAX_HEIGHT+1):
			max_seq_val = max(max_seq_val, dp[i][j])
		
	# Return the maximum sequence value.
	return max_seq_val

Happy Learning – If you require any further information, feel free to contact me.