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

ধরুন আমাদের একটি অনির্দেশিত গ্রাফ আছে যা আমাদের পরীক্ষা করতে হবে যে আমরা এটির ভিতরে একটি বিজোড় দৈর্ঘ্যের চক্র খুঁজে পাচ্ছি কি না৷

সুতরাং, যদি ইনপুট হয় adj_list =[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

তাহলে আউটপুট সত্য হবে কারণ [0, 1, 3, 4, 2], [1, 3, 4], [2, 3, 4] এর মতো বিজোড় দৈর্ঘ্যের চক্র রয়েছে।

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড নেবে, i
• যদি নোড পাথে থাকে, তাহলে
  • যখন (i - পাথ[নোড]) বিজোড় হয় তখন সত্য প্রত্যাবর্তন করুন
• যদি নোড পরিদর্শন করা হয়, তাহলে
  • মিথ্যে ফেরত দিন
• নোডকে পরিদর্শন করা হিসাবে চিহ্নিত করুন
• পথ[নোড] :=i
• arr[নোড]-এ প্রতিটি c-এর জন্য, do
  • যদি dfs(c, i + 1) সত্য হয়, তাহলে
    • সত্য ফেরান
• ডেল পাথ[নোড]
• মিথ্যে ফেরত দিন
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
• পরিদর্শন করেছেন :=একটি নতুন সেট, পথ :=একটি নতুন মানচিত্র
• আমি 0 থেকে arr-এর মাপ রেঞ্জের জন্য, কর
• যদি 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