1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
| #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); typedef pair<int, int> pii; typedef long long LL; const double PI = acos(-1.0); const int N = 3e5 + 7; struct edge { int to, nxt; edge() {} edge(int _to, int _nxt): to(_to), nxt(_nxt) {} } E[N]; int head[N], tot; int ch[N], cycle, d[N][26], vis[N], Ans; char s[N];
void init() { CLR(head, -1); } inline void add(int s, int t) { E[tot] = edge(t, head[s]); head[s] = tot++; } namespace tarjan { int dfn[N], low[N], st[N], sc, top, sccnt, scnum[N]; bool ins[N]; void tar(int u) { if (cycle) return ; dfn[u] = low[u] = ++sc; st[top++] = u; ins[u] = true; register int v; for (register int i = head[u]; ~i; i = E[i].nxt) { v = E[i].to; if (!dfn[v]) { tar(v); low[u] = min(low[u], low[v]); } else if (ins[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { ++sccnt; do { v = st[--top]; ins[v] = false; if (++scnum[sccnt] > 1) { cycle = 1; return ; } } while (u != v); } } } void dfs(int u) { vis[u] = 1; d[u][ch[u]] = 1; for (register int i = head[u]; ~i; i = E[i].nxt) { int v = E[i].to; if (!vis[v]) dfs(v); for (register int k = 0; k < 26; ++k) { d[u][k] = max(d[u][k], d[v][k] + (k == ch[u])); Ans = max(Ans, d[u][k]); } } } int main(void) { init(); register int n, m, i, a, b; scanf("%d%d", &n, &m); scanf("%s", s + 1); for (i = 1; i <= n; ++i) ch[i] = s[i] - 'a'; for (i = 0; i < m; ++i) { scanf("%d%d", &a, &b); if (cycle) continue; add(a, b); if (a == b) cycle = 1; } if (cycle) { return puts("-1"); } for (i = 1; i <= n && !cycle; ++i) { if (!tarjan::dfn[i]) { tarjan::tar(i); } } if (cycle) { return puts("-1"); } for (i = 1; i <= n; ++i) { if (!vis[i]) dfs(i); } for (i = 1; i <= n; ++i) for (a = 0; a < 26; ++a) Ans = max(Ans, d[i][a]); cout << Ans << endl; return 0; }
|