পাইথনে গ্রাফ ট্রি সংগ্রহ (ফরেস্ট) কিনা যাচাই করার প্রোগ্রাম

ধরা যাক একটি গ্রাফ আছে এজ লিস্ট হিসেবে। গ্রাফটি ট্রির সংগ্রহ (ফরেস্ট) কিনা যাচাই করতে হবে।

উদাহরণ এজ লিস্ট হলে আউটপুট True।

সমাধানের ধাপসমূহ

• dfs(node, prev) ফাংশন: যদি node seen-এ থাকে, False ফেরত দিন। seen-এ node যোগ করুন। adj[node]-র প্রতিটি adjacent n-এর জন্য: যদি n != prev এবং dfs(n, node) false হয়, False ফেরত দিন। True ফেরত দিন।
• মূল মেথড: e := ডিফল্টডিক্ট(লিস্ট), এজগুলো থেকে এডজেসেন্সি লিস্ট বানান। seen := সেট। প্রতিটি node-এ জন্য: যদি node seen-এ না থাকে এবং dfs(node, -1) false হয়, False ফেরত দিন। True ফেরত দিন।

উদাহরণ কোড

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