পাইথনে DAG-এ নোড পুনরাবৃত্তি ছাড়া সর্বোচ্চ দৈর্ঘ্যের পাথ খুঁজে বের করার প্রোগ্রাম

একটি নির্দেশিত চক্রবিহীন গ্রাফ (DAG) এডজেসেন্সি লিস্ট হিসেবে দেওয়া আছে। আমাদের লক্ষ্য হল গ্রাফে এমন একটি পাথ খুঁজে বের করা যাতে কোনো নোড দুবার ভিজিট না করা হয় এবং পাথটির দৈর্ঘ্য (এজ সংখ্যা) সর্বোচ্চ হয়।

উদাহরণস্বরূপ, নিচের গ্রাফের জন্য আউটপুট ৪:

graph = [[1, 2], [3, 4], [], [4], [2]]

সর্বোচ্চ পাথ: 0 → 1 → 3 → 4 → 2 (৪টি এজ)।

সমাধানের পদ্ধতি (DFS + মেমোরাইজেশন / DP on DAG)

1. ans = 0, n = len(graph)।
2. table = [-1] * n (মেমোরাইজেশন টেবিল)。——
3. dfs(u) ফাংশন ডিফাইন করুন:
   • যদি table[u] != -1 হয়, তবে ক্যাশড মান রিটার্ন করুন।
   • p_len = 0।
   • প্রতিটি সন্নিকট নোড v এর জন্য graph[u]-এ: p_len = max(p_len, 1 + dfs(v))।
   • table[u] = p_len সংরক্ষণ করে রিটার্ন করুন।
4. প্রতিটি নোড i (০ থেকে n-1) এর জন্য ans = max(ans, dfs(i))।
5. ans রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, graph):
        ans = 0
        n = len(graph)
        table = [-1] * n
        def dfs(u):
            if table[u] != -1:
                return table[u]
            p_len = 0
            for v in graph[u]:
                p_len = max(p_len, 1 + dfs(v))
            table[u] = p_len
            return p_len
        for i in range(n):
            ans = max(ans, dfs(i))
        return ans

ob = Solution()
graph = [[1, 2], [3, 4], [], [4], [2]]
print(ob.solve(graph))

ইনপুট

graph = [[1, 2], [3, 4], [], [4], [2]]

আউটপুট

4