পাইথনে নির্দেশিত গ্রাফে সবচেয়ে বড় রঙের মান খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের n রঙিন নোড এবং m বিভিন্ন প্রান্ত সহ একটি নির্দেশিত গ্রাফ রয়েছে। এবং নোডগুলি 0 থেকে n-1 পর্যন্ত সংখ্যাযুক্ত। আমাদের কাছে ছোট হাতের অক্ষর সহ একটি স্ট্রিং কোল রয়েছে, যেখানে col[i] এই গ্রাফের ith নোডের রঙকে প্রতিনিধিত্ব করে (0-সূচীযুক্ত)। আমাদের কাছে একটি প্রান্ত তালিকাও রয়েছে যেখানে প্রান্ত [j] =(u, v) প্রতিনিধিত্ব করে, সেখানে u এবং v এর মধ্যে একটি প্রান্ত রয়েছে।

গ্রাফে একটি বৈধ পথ হল 1 থেকে k পর্যন্ত সমস্ত i-এর জন্য নোড xi-এর একটি ক্রম, যেমন xi থেকে xi+1 পর্যন্ত একটি নির্দেশিত প্রান্ত রয়েছে। পথের রঙ হল সেই পথের সবচেয়ে ঘন ঘন নোডের রঙ। আমাদের সেই গ্রাফে যেকোনো বৈধ পথের সবচেয়ে বড় রঙের মান খুঁজে বের করতে হবে। যদি গ্রাফে একটি চক্র থাকে তবে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুটটি হয় col ="aabada" edges =[(0,1),(1,4),(1,2),(2,3),(3,5),(4,5) ],

তাহলে আউটপুট হবে 4 হিসাবে 0 -> 1 -> 2 -> 3 -> 5-এ 'a' রঙ সহ দীর্ঘতম পথ রয়েছে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n:=কলের আকার

• গ্রাফ:=প্রান্ত তালিকা থেকে প্রদত্ত গ্রাফ

• indegree:=নোড এবং তাদের ইন-ডিগ্রি মান সম্বলিত মানচিত্র

• সারি:=একটি নতুন তালিকা

• dp:=n x 26 আকারের একটি অ্যারে তৈরি করুন এবং 0

  দিয়ে পূরণ করুন

• colorvalues:=col এর সমস্ত c এর জন্য বর্ণমালায় c এর ক্রম সহ একটি তালিকা তৈরি করুন

• আপনার জন্য 0 থেকে n - 1 রেঞ্জে, করুন

  • আপনি যদি অসম্পূর্ণ না হন, তাহলে

    • সারির শেষে u ঢোকান

    • dp[u, colorvalues[u]]:=1

• পরিদর্শন করেছেন:=0

• সারি খালি না থাকার সময়, করুন

  • u:=সারির সামনের উপাদান এবং পরে এটি মুছুন

  • পরিদর্শন করেছেন :=পরিদর্শন করেছেন + 1

  • গ্রাফ[u]-এ প্রতিটি v-এর জন্য করুন

    • 0 থেকে 25 রেঞ্জে c এর জন্য, করুন

      • dp[v, c] =সর্বাধিক dp[v, c] এবং (dp[u, c] + (1 যদি c একই রঙের মান [v] হয়, অন্যথায় 0)

    • indegree[v] :=indegree[v] - 1

    • যদি indegree[v] 0 এর সমান হয়, তাহলে

      • সারির শেষে v সন্নিবেশ করান

      • del indegree[v]

• যদি পরিদর্শন করা হয়

  • রিটার্ন -1

• dp

  -এ সর্বাধিক উপাদান ফেরত দিন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

from collections import defaultdict
def solve(col, edges):
   n=len(col)
   graph=defaultdict(list)
   indegree=defaultdict(int)

   for u,v in edges:
      graph[u].append(v)
      indegree[v]+=1

   queue=[]
   dp=[[0]*26 for _ in range(n)]
   colorvalues=[ord(c)-ord("a") for c in col]
   for u in range(n):
      if u not in indegree:
         queue.append(u)
         dp[u][colorvalues[u]]=1

   visited=0
   while queue:
      u=queue.pop()
      visited+=1

      for v in graph[u]:
         for c in range(26):
            dp[v][c]=max(dp[v][c],dp[u][c] + (c==colorvalues[v]))
         indegree[v]-=1
         if indegree[v]==0:
            queue.append(v)
            del indegree[v]
   if visited<n:
      return -1
   return max(max(x) for x in dp)

col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges))

ইনপুট

"aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]

আউটপুট

4