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.

CONSTRAINTS:

1 < N,M < 300000

**FUNCTION DESCRIPTION: **

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);
    w[u].push_back(v);
    ++deg[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();
    que.pop();
    for (int v : w[u]) {
    if (–deg[v] == 0)
    que.push(v), ++ct;
    }
    }
    if (ct < n) {
    puts("-1");
    } 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;
    }

LEAVE A COMMENT