Is there any solution to find beautiful path by given information? [closed]

  c++, java

Given a directed graph with N nodes and M edges. Each node is associated with lowercase english alphabet. Beauty of a path is defined as the number of most frequently occurring alphabet. Find the most beautiful path and return the maximum beauty value it has.


1 < N,M < 300000


Complete the function beauty in code. Function must Return an integer, the beauty of most beautiful path. If the value is very large return -1.

Function beauty has the following parameter(s):

n: integer, number of nodes

m: integer, number of directed edges

S: string of length n where ith alphabet denotes the alphabets associated with ith node

X: list of length m

Y: list of length m

Source: Windows Questions C++

2 thoughts on - Is there any solution to find beautiful path by given information? [closed]

  • #include
    using namespace std;
    const int maxn = 300011;
    char s[maxn];
    int deg[maxn], d[maxn];
    vector w[maxn];
    int Find(int u, int c) {
    if (d[u] != -1) return d[u];
    d[u] = 0;
    for (int v : w[u]) {
    d[u] = max(d[u], Find(v, c));
    d[u] += (s[u] == c + ‘a’);
    return d[u];
    int main() {
    int n, m;
    scanf(“%d%d”, &n, &m);
    scanf(“%s”, s + 1);
    for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    int ct = 0;
    queue que;
    for (int i = 1; i <= n; ++i) {
    if (!deg[i])
    que.push(i), ++ct;
    while (!que.empty()) {
    int u = que.front();
    for (int v : w[u]) {
    if (–deg[v] == 0)
    que.push(v), ++ct;
    if (ct < n) {
    } else {
    int ans = 0;
    for (int c = 0; c < 26; ++c) {
    memset(d, 0xff, sizeof d);
    for (int i = 1; i <= n; ++i)
    ans = max(ans, Find(i, c));
    printf("%d\n", ans);
    return 0;