पायथन में बिंदुओं के समूह को K अलग-अलग समूहों में बांटने का प्रोग्राम

मान लीजिए हमारे पास बिंदुओं की एक सूची और एक संख्या k है। बिंदु (x, y) के रूप में कार्टेशियन निर्देशांक दर्शाते हैं। हम किन्हीं दो बिंदुओं p1 और p2 को समूहित कर सकते हैं यदि उनके बीच यूक्लिडियन दूरी k से कम या बराबर है। हमें असंयुक्त समूहों की कुल संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट points = [[2,2],[3,3],[4,4],[11,11],[12,12]], k = 2 है, तो आउटपुट 2 होगा, क्योंकि यह दो समूह बना सकता है: ([2,2],[3,3],[4,4]) और ([11,11],[12,12])।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (ग्राफ + DFS):

dfs(i) फ़ंक्शन परिभाषित करें।
यदि i seen में है, तो लौटें।
seen.add(i)।
प्रत्येक nb के लिए adj[i] में: dfs(nb)।
मुख्य विधि से:
- adj := डिफॉल्टडिक्ट(list)।
- n := len(points)।
- j को 0 से n-1 तक, i को 0 से j-1 तक:
  - x1,y1 = points[i]; x2,y2 = points[j]।
  - यदि (x1-x2)^2 + (y1-y2)^2 <= k^2, तो adj[i].append(j) और adj[j].append(i)।
- seen := set(), ans := 0।
- i को 0 से n-1 तक: यदि i not in seen, तो ans += 1; dfs(i)।
- ans लौटाएं।

उदाहरण

from collections import defaultdict class Solution:    def solve(self, points, k):       adj = defaultdict(list)       n = len(points)       for j in range(n):          for i in range(j):             x1, y1 = points[i]             x2, y2 = points[j]             if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= k ** 2:                adj[i].append(j)                adj[j].append(i)       seen = set()       def dfs(i):          if i in seen:             return          seen.add(i)          for nb in adj[i]:             dfs(nb)       ans = 0       for i in range(n):          if i not in seen:             ans += 1             dfs(i)       return ans ob = Solution() points = [ [2, 2], [3, 3], [4, 4], [11, 11], [12, 12] ] k = 2 print(ob.solve(points, k))

इनपुट

[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]],2