মনে করুন আমাদের কাছে n সংখ্যক রঙিন নোড এবং m সংখ্যক ভিন্ন এজ সহ একটি ডায়রেক্টেড গ্রাফ আছে। নোডগুলো 0 থেকে n-1 পর্যন্ত নম্বর করা আছে। আমাদের কাছে ছোট হাতের অক্ষरों সহ একটি স্ট্রিং col আছে, যেখানে col[i] এই গ্রাফে i-তম নোডের রঙ প্রতিনিধিত্ব করে (0-ইন্ডেক্সড)। আমাদের কাছে একটি এজ লিস্টও আছে যেখানে edges[j] = (u, v) নির্দেশ করে, u এবং v-এর মধ্যএ একটি এজ আছে।
গ্রাফে একটি বৈধ পথ হল xi নোডের সিকোয়েন্স যা i=1 থেকে k পর্যন্ত সব জন্য, যাতে 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 := col-এর সাইজ
graph := এজ লিস্ট থেকে দেওয়া গ্রাফ
indegree := নোড এবং তাদের ইন-ডিগ্রী মান ধারণকারী ম্যাপ
queue := একটি নতুন তালিকা
dp := n x 26 আকারের একটি অ্যারে তৈরি করুন এবং 0 দিয়ে পূরণ করুন
colorvalues := col-এ সব c-এর জন্য অ্যালফাবেটে c-এর ক্রম নিয়ে একটি তালিকা বানান
u = 0 থেকে n-1 পর্যন্ত জন্য, করুন
যদি u indegree-তে না থাকে, তবে
queue-এর শেষে u যোগ করুন
dp[u, colorvalues[u]] := 1
visited := 0
যতক্ষণ queue খালি নয়, করুন
u := queue-এর ফ্রন্ট এলিমেন্ট এবং এরপর মুছে দিন
visited := visited + 1
graph[u]-এ প্রতিটি v-এর জন্য, করুন
c = 0 থেকে 25 পর্যন্ত জন্য, করুন
dp[v, c] = dp[v, c] এবং (dp[u, c] + (1 যদি c colorvalues[v]-এর সমান হয়, অন্যথায় 0) এর মধ্যে সর্বোচ্চ
indegree[v] := indegree[v] - 1
যদি indegree[v] 0-এর সমান হয়, তবে
queue-এর শেষে v যোগ করুন
del indegree[v]
যদি visited < n হয়, তবে
-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
