Computer Science, asked by ravalishetty8, 1 month ago

Given a directed graph with N nodes and Medges. Each node isassociated 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.​ in python​

Answers

Answered by shraddhasurvase35
12

Answer:

You are given a graph with n nodes and 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. Your task is find a path whose value is the largest.

Explanation:

Answered by sujan3006sl
19

Answer:

def binomialCoeff(n, k):

   if (k > n):

       return 0

   res = 1

   if (k > n - k):

       k = n - k

   for i in range( k):

       res *= (n - i)

       res //= (i + 1)

   return res

if __name__=="__main__":

   N = 5

   M = 1

   P = (N * (N - 1)) // 2

   print(binomialCoeff(P, M))

Explanation:

  • From 1 to N, the N vertices are numbered. The edge must be present between two separate vertices because there are no self-loops or duplicate edges. So there are NC2 ways to pick two alternative vertices, which is equivalent to (N * (N – 1) / 2. Let's assume it's P.
  • M edges must now be employed with these pairs of vertices, resulting in PCM methods to pick M pairs of vertices between P pairs.
  • If P = M, the solution will be 0 since the extra edges can't be ignored.

#SPJ3

Similar questions