Maximum path - MarisaOJ: Marisa Online Judge

HOME
PROBLEMSET
ROADMAP
COMPETITION
TOPIC
RANKING
GUIDE
MASHUP
ABOUT
CONTACT

Given an directed acyclic graph (DAG). Each vertex is assigned a lowercase letter. A path's value is the number of most frequently occuring letter. For example,

$marisa$ , the value should be

$2$ as letter

$a$ occurs

$2$ times. ### Input - The first line contains two integers

$n,m$ . - The second line contains a string. The

$i^{th}$ character is the letter assigned to vertex

$i$ . - The next

$m$ lines, each line contains two integers

$u, v$ an edge directed from

$u$ to

$v$ . ### Output - Print the maximum value among all paths. ### Constraints -

$1 \le n,m \le 10^5$ . -

$1 \le u,v\le n$ . ### Example Input:

$5 4 abaca 1 2 1 3 3 4 4 5$

Output:

$3$

DAG / Topological sort
	DAG
	Reading order
	Longest path
	Maximum path
	Martian language
	Edge direction
	Train pass

Topic

Graph

Dynamic Programming

Rating

1400

Source

Codeforces

Solution (0)

Solution