本文共 2457 字，大约阅读时间需要 8 分钟。

D. Substring

time limit: per test3 seconds

memory limit: per test256 megabytes

inputstandard: input

outputstandard: output

You are given a graph with

$$

n

n

nodes and

$$

m

m

directed edges. One lowercase letter is assigned to each node. We define a path’s value as the number of the most frequently occurring letter. For example, if letters on a path are “abaca”, then the value of that path is

$$

3

3

. Your task is find a path whose value is the largest.

Input

The first line contains two positive integers

$$

n

,

m

(

1

≤

n

,

m

≤

300000

)

n,m (1≤n,m≤300000)

, denoting that the graph has

$$

n

n

nodes and

$$

m

m

directed edges.

The second line contains a string

$$

s

s

with only lowercase English letters. The

$$

i

i

-th character is the letter assigned to the

$$

i

i

-th node.

Then m lines follow. Each line contains two integers

$$

x

,

y

(

1

≤

x

,

y

≤

n

)

x,y (1≤x,y≤n)

, describing a directed edge from

$$

x

x

to

$$

y

y

. Note that

$$

x

x

can be equal to

$$

y

y

and there can be multiple edges between

$$

x

x

and

$$

y

y

. Also the graph can be not connected.

Output

Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output

$$

−

1

-1

instead.

Examples

input

5 4abaca1 21 33 44 5

output

3

input

6 6xzyabc1 23 12 35 44 36 4

output

-1

input

10 14xzyzyzyzqx1 22 43 54 52 66 86 52 103 910 94 61 102 83 7

output

4

Note

In the first sample, the path with largest value is

$$

1

→

3

→

4

→

5

1→3→4→5

. The value is

$$

3

3

because the letter ‘a’ appears

$$

3

3

times.

题意

给出有

$$

n

n

个点和

$$

m

m

条边的有向图，每个节点上有一个小写字母，求所有通路中出现次数最多的字母出现的次数，如果出现了无数次，输出

$$

−

1

-1

Solve

用拓扑排序判断图中是否有环，如果有环，那么环上的字母出现的次数为无限多次，输出

$$

−

1

-1

。如果能够进行拓扑排序，对于每次遍历的节点，更新当前路上字母出现次数的最大值

$$

d

p

[

i

]

[

j

]

dp[i][j]

表示到达节点

$$

i

i

，字母

$$

′

a

′

+

j

'a'+j

出现的最大次数

Code

#include 
   
    #define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define INF 0x7f7f7f7fconst int maxn=1e6+10;const int mod=1e9+7;using namespace std;int n,m;char ch[maxn];int visi[maxn];// dp[i][j]表示到i位置，字母j出现的最多次数int dp[maxn][50];int cnt;vector
    
     v[maxn];queue
     
      que;void topo(){	for(int i=1;i<=n;i++)		if(!visi[i])		{			que.push(i);			dp[i][ch[i]-'a']++;		}	while(!que.empty())	{		cnt++;		int res=que.front();		que.pop();		int sz=v[res].size();		for(int i=0;i
      
       >n>>m;	cin>>(ch+1);	ms(visi,0);	int x,y;	for(int i=0;i
       
        >x>>y;		v[x].push_back(y);		visi[y]++;	}	topo();	return 0;}
       
      
     
    
   

转载地址：https://www.cnblogs.com/Friends-A/p/11054967.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！