পাইথনে ন্যূনতম খরচে সিটি কানেক্ট করা

মনে করুন N সংখ্যক সিটি রয়েছে ১ থেকে N পর্যন্ত নম্বর করা। আমাদের connections আছে, যেখানে প্রতিটি connection[i] হলো [city1, city2, cost] যা city1 এবং city2 কানেক্ট করার খরচ বোঝায়। আমাদের ন্যূনতম খরচ বের করতে হবে যাতে প্রতিটি সিটি জোড়ার জন্য কম-বেশি একটি পাথ থাকে (লেঞ্জ ১ হলেও চলে) যা সেগুলো কানেক্ট করে। খরচ হলো ব্যবহৃত কানেকশন খরচের যোগফল। যদি অসম্ভব হয়, তবে -1 রিটার্ন করুন।

গ্রাফ যদি নিচের মতো হয়:

তবে আউটপুট হবে 6, যেকোনো দুটি সিটি বেছে নিলে সকল সিটি কানেক্ট হয়, তাই আমরা ন্যূনতম ২টি বেছে নিই, [1, 5]।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (Kruskal's Algorithm / Union-Find):

• find(x) মেথড ডিফাইন করুন:

  • যদি parent[x] == -1, তবে return x

  • parent[x] := find(parent[x])

  • return parent[x]

• union(x, y) মেথড ডিফাইন করুন:

  • parent_x := find(x), parent_y := find(y)

  • যদি parent_x == parent_y, তবে রিটার্ন, অন্যথায় parent[parent_y] := parent_x

• মেইন মেথড n এবং conn নেবে:

  • parent := size n অ্যারে, -1 দিয়ে পূরণ, disjoint := n - 1, cost := 0

  • c := sorted conn, cost অনুযায়ী সর্টেড

  • i := 0

  • while i < len(c) and disjoint != 0

    • x := c[i][0], y := c[i][1]

    • যদি find(x) != find(y), তবে disjoint--, cost += c[i][2], এবং union(x, y)

    • i++

  • return cost if disjoint == 0 else -1

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

class Solution(object):
    def find(self, x):
        if self.parent[x] == -1:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        parent_x = self.find(x)
        parent_y = self.find(y)
        if parent_x == parent_y:
            return
        self.parent[parent_y] = parent_x

    def minimumCost(self, n, connections):
        self.parent = [-1 for i in range(n+1)]
        disjoint = n - 1
        cost = 0
        c = sorted(connections, key=lambda v: v[2])
        i = 0
        while i < len(c) and disjoint:
            x = c[i][0]
            y = c[i][1]
            if self.find(x) != self.find(y):
                disjoint -= 1
                cost += c[i][2]
                self.union(x, y)
            i += 1
        return cost if not disjoint else -1

ob = Solution()
print(ob.minimumCost(3, [[1,2,5], [1,3,6], [2,3,1]]))

ইনপুট

3 [[1,2,5],[1,3,6],[2,3,1]]

আউটপুট

-1