প্রদত্ত গ্রাফ পরীক্ষা করার প্রোগ্রামটি গাছের একটি সেট নাকি পাইথনে নয়

ধরুন আমাদের একটি গ্রাফ আছে, যা প্রান্তের তালিকা হিসাবে উপস্থাপন করা হয়েছে। গ্রাফটি গাছের (বন) সংগ্রহ কিনা তা আমাদের পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে True

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড নেবে, পূর্বে

• যদি নোড দেখা যায়, তাহলে

  • রিটার্ন ফলস

• দেখাতে নোড সন্নিবেশ করান

• প্রতিটি সংলগ্ন নোডের জন্য n e[নোড], করুন

  • যদি n আগের মত না হয়, তাহলে

    • যদি dfs(n, node) মিথ্যা হয়, তাহলে

      • রিটার্ন ফলস

• রিটার্ন ট্রু

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• e :=একটি খালি মানচিত্র

• প্রতিটি স্টার্ট নোড u এবং প্রান্তে শেষ নোড v এর জন্য, করুন

  • e[u]

    এর শেষে v সন্নিবেশ করান

  • e[v]

    এর শেষে u ঢোকান

• দেখা হয়েছে :=একটি নতুন সেট

• e-এর প্রতিটি নোডের জন্য করুন

  • যদি নোড দেখা না যায় এবং dfs(নোড, -1) মিথ্যা হয়, তাহলে

    • রিটার্ন ফলস

• রিটার্ন ট্রু

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

from collections import defaultdict
class Solution:
   def solve(self, edges):
      e = defaultdict(list)
      for t,f in edges:
         e[t].append(f)
         e[f].append(t)

      seen = set()

      def dfs(node, prev):
         if node in seen:
            return False
         seen.add(node)
      for adj in e[node]:
         if adj != prev:
            if not dfs(adj, node):
               return False
      return True

   for node in e:
      if node not in seen and not dfs(node, -1):
         return False
   return True

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

ইনপুট

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

আউটপুট

True