मान लीजिए हमें एक भारित, अविकल्पित ग्राफ दिया गया है। हमें एक फ़ंक्शन 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) return 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
