पायथन में बिंदुओं के एक समूह को k विभिन्न समूहों में समूहित करने का कार्यक्रम

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें dfs() । इसमें मुझे लगेगा

• अगर मैं दिख रहा हूँ, तो

  • वापसी

  • मैंने देखा में डालें

  • adj[i] में प्रत्येक nb के लिए, करें

    • डीएफएस(एनबी)

    • मुख्य विधि से, निम्न कार्य करें-

    • adj :=एक नक्शा

    • n :=बिंदुओं का आकार

    • j के लिए 0 से n की सीमा में, करें

      • मेरे लिए 0 से j की सीमा में, ऐसा करें

        • p1:=अंक[i]

        • p2 :=अंक[j]

        • यदि यूक्लिडियन p1 और p2

          • adj[i]

            . के अंत में j डालें

          • adj[j]

            . के अंत में i डालें

    • देखा :=एक नया सेट

    • उत्तर :=0

    • मेरे लिए 0 से n की सीमा में, करें

      • अगर मैंने नहीं देखा, तो

        • उत्तर:=उत्तर + 1

        • dfs(i)

    • वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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

आउटपुट

2