মনে করুন, আমাদের কাছে একটি ওজনযুক্ত, আনডায়রেক্টেড গ্রাফ দেওয়া আছে। আমাদের একটি query ফাংশন ইমপ্লিমেন্ট করতে হবে যা দুটি ভার্টেক্স এবং একটি খরচ 'limit' ইনপুট হিসেবে নেবে এবং চেক করবে কি ইনপুট দিয়া খরচের চেয়ে কম খরচের পথ আছে কিনা। যদি পথ থাকে তবে true রিটার্ন করব, অন্যথায় false।
সুতরাং, যদি ইনপুট হয়
এবং কোয়েরিগুলো হল (0, 2, 10), (3, 1, 30), (4, 3, 30)।
তবে আউটপুট হবে
False True True
প্রথম কোয়েরির ফলাফল False কারণ ভার্টেক্স 0 থেকে 2-এ 10 খরচের কোনো পথ নেই।
দ্বিতীয় কোয়েরির ফলাফল True কারণ ভার্টেক্স 3 থেকে 1-এ 10 খরচের একটি পথ আছে, যা 30-র চেয়ে কম।
তৃতীয় কোয়েরির ফলাফল True কারণ ভার্টেক্স 4 থেকে 3-এ 30 খরচের একটি পথ আছে, যা 30-র সমান।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
weights := গ্রাফে থাকা বিভিন্ন ওজনের একটি তালিকা
connections := ওজনগুলোর জন্য কানেকশনের একটি তালিকা
query() ফাংশন ডিফাইন করুন। এটি p, q, limit নেবে
index := weights-এ वो পজিশন যেখানে limit বাম পাশে ইনসার্ট করা যায় সর্টেড অর্ডার মেইনটেইন করে
যদি index == 0 হয়, তবে
False রিটার্ন করুন
connections[index-1, p] == connections[index-1, q] হলে True রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −
import bisect
class Solution(object):
def __init__(self, n, edgeList):
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(x, y):
parent[find(y)] = find(x)
parent = {i: i for i in range(n)}
edgeList.sort(key=lambda x: x[2])
self.connections = []
self.weights = []
for index, (i, j, weight) in enumerate(edgeList):
union(i, j)
if index != len(edgeList)-1 and weight == edgeList[index+1][2]:
continue
self.weights.append(weight)
self.connections.append([find(i) for i in parent])
def query(self, p, q, limit):
index = bisect.bisect_left(self.weights, limit)
if index == 0:
return False
return self.connections[index-1][p] == self.connections[index-1][q]
ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])
print(ob.query(0, 2, 10))
print(ob.query(3, 1, 30))
print(ob.query(4, 3, 30))
ইনপুট
ob = Solution(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]]) print(ob.query(0, 2, 10)) print(ob.query(3, 1, 30)) print(ob.query(4, 3, 30))
আউটপুট
False True True
