পাইথনে আনডিরেক্টেড গ্রাফে বিজোড় দৈর্ঘ্যের সাইকেল আছে কিনা যাচাই করার প্রোগ্রাম

একটি আনডিরেক্টেড গ্রাফ (এডজেসেন্সি লিস্ট) দেওয়া আছে। গ্রাফে বিজোড় দৈর্ঘ্যের সাইকেল আছে কিনা সেটি বের করতে হবে।

উদাহরণস্বরূপ, adj_list = [[1,2],[0,3,4],[0,3,4],[1,2,4],[1,2,3]] হলে আউটপুট True (সাইকেল: [0,1,3,4,2], [1,3,4], [2,3,4])।

সমাধানের পদ্ধতি (DFS + পাথ লেংথ ট্র্যাকিং)

1. visited সেট, path ডিকশনারি (নোড -> ডেপথ)।
2. dfs(node, depth):
   • যদি node in path: সাইকেল দৈর্ঘ্য = depth - path[node]। বিজোড় হলে True।
   • যদি node in visited: False।
   • visited.add(node); path[node] = depth।
   • নেইবরদের জন্য রিকার্সিভ কল। যদি True রিটার্ন করলে True।
   • del path[node]; return False।
3. সব নোড থেকে dfs(i, 0) কল করুন।

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

class Solution:
    def solve(self, arr):
        def dfs(node, i):
            if node in path:
                return (i - path[node]) % 2 == 1
            if node in visited:
                return False
            visited.add(node)
            path[node] = i
            for c in arr[node]:
                if dfs(c, i + 1):
                    return True
            del path[node]
            return False
        visited, path = set(), {}
        for i in range(len(arr)):
            if dfs(i, 0):
                return True
        return False

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

ইনপুট

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

আউটপুট

True