পাইথনে একটি এজ মিনিমাম স্প্যানিং ট্রির অংশ কিনা চেক করা

একটি অনডিরেক্টেড ওয়েটেড গ্রাফ দেওয়া আছে edges = [[u,v,w],...]। একটি এজ (a,b) দেওয়া আছে। এটিই কি কোনো মিনিমাম স্প্যানিং ট্রি (MST)-র অংশ হতে পারে তা বের করতে হবে। গ্রাফ কানেক্টেড এবং এজটি গ্রাফে আছে বলে ধরা হয়।

উদাহরণ: edges=[[0,2,100],[1,2,200],[1,3,100],[2,3,300]], a=0, b=2 → আউটপুট True।

সমাধানের ধাপসমূহ (MST প্রপার্টি: সাইকেল প্রপার্টি / কাট প্রপার্টি)

1. দেওয়া এজ (a,b)-এর ওয়েট weight বের করুন।

2. সকল এজ যাদের ওয়েট weight-এর চেয়ে স্ট্রিক্টলি কম, সেগুলো নিয়ে একটি সাবগ্রাফ বানান।

3. সাবগ্রাফে a থেকে b পর্যন্ত পথ আছে কিনা চেক করুন (DFS/BFS)।

4. যদি পথ নেই, তবে এজটি MST-র অংশ (Cut Property)।

5. যদি পথ রहे, তবে এজটি MST-র অংশ নয় (Cycle Property)।

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

class Solution:
    def findPath(self, edges, a, b):
        if a == b:
            return True
        if not edges:
            return False
        for x in edges:
            if x[2] == -1:
                continue
            new_a = -1
            if x[0] == a:
                new_a = x[1]
            elif x[1] == a:
                new_a = x[0]
            if new_a != -1:
                edges.remove(x)
                if self.findPath(edges, new_a, b):
                    return True
                edges.append(x)
        return False
    def solve(self, edges, a, b):
        weight = next(x for x in edges if (x[0] == a and x[1] == b) or (x[1] == a and x[0] == b))[2]
        edges = [x for x in edges if x[2] < weight]
        return not self.findPath(edges, a, b)

ob = Solution()
print(ob.solve([[0, 2, 100], [1, 2, 200], [1, 3, 100], [2, 3, 300]], 0, 2))

ইনপুট

[[0,2,100],[1,2,200],[1,3,100],[2,3,300]], 0, 2

আউটপুট

True