পাইথনে নির্দিষ্ট নোড ধারণকারী ন্যূনতম সাইকেলের দৈর্ঘ্য বের করার প্রোগ্রাম

একটি নির্দেশিত গ্রাফের এডজেসেন্সি লিস্ট এবং একটি টার্গেট নোড দেওয়া আছে। টার্গেট নোড ধারণকারী সবচেয়ে ছোট সাইকেলের দৈর্ঘ্য বের করুন। না থাকলে -1।

উদাহরণ: গ্রাফ [[1,4],[2],[3],[0,1],[]], টার্গেট ৩ → আউটপুট ৩ (সাইকেল ১→২→৩→১)।

সমাধানের ধাপগুলো:

BFS দিয়ে টার্গেট থেকে শুরু করে লেভেল বে লেভেল ভিজিট করুন।
যদি টার্গেট tekrar পাওয়া যায় তবে লেভেল রিটার্ন করুন।
ভিজিটেড সেট ব্যবহার করুন।

উদাহরণ

class Solution:
    def solve(self, graph, target):
        visited = set()
        l = [target]
        length = 0
        while l:
            length += 1
            nl = []
            for u in l:
                for v in graph[u]:
                    if v == target:
                        return length
                    if v in visited:
                        continue
                    visited.add(v)
                    nl.append(v)
            l = nl
        return -1

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

ইনপুট

[[1, 4],[2],[3],[0, 1],[]]