दिए गए ग्राफ की जांच करने का कार्यक्रम पायथन में पेड़ों का एक समूह है या नहीं

मान लीजिए कि हमारे पास एक ग्राफ है, जिसे किनारों की सूची के रूप में दर्शाया गया है। हमें यह जांचना होगा कि ग्राफ पेड़ों (जंगल) का संग्रह है या नहीं।

तो, अगर इनपुट पसंद है

तो आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा, पिछला

• यदि नोड दिखाई दे, तो

  • झूठी वापसी

• देखा में नोड डालें

• ई [नोड] में प्रत्येक आसन्न नोड एन के लिए, करें

  • यदि n पिछले के समान नहीं है, तो

    • अगर dfs(n, node) गलत है, तो

      • झूठी वापसी

• सही लौटें

• मुख्य विधि से, निम्न कार्य करें -

• e :=एक खाली नक्शा

• प्रत्येक प्रारंभ नोड के लिए u और अंत नोड v किनारों में, करें

  • e[u]

    . के अंत में v डालें

  • e[v]

    . के अंत में आपको सम्मिलित करें

• देखा :=एक नया सेट

• ई में प्रत्येक नोड के लिए, करें

  • यदि नोड नहीं देखा जाता है और 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