ধরা যাক পয়েন্টের একটি তালিকা এবং একটি সংখ্যা k আছে। পয়েন্টগুলো (x, y) কারtezian কোঅর্ডিনেট। দুটি পয়েন্ট 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(i) ফাংশন: যদি i seen-এ থাকে, ফেরত দিন। seen-এ i যোগ করুন, adj[i]-র প্রতিটি nb-এর জন্য dfs(nb) কল করুন।
- মূল মেথড: adj := ডিফল্টডিক্ট(লিস্ট), n := len(points)
- j = 0 থেকে n-1, i = 0 থেকে j-1 পর্যন্ত: p1=points[i], p2=points[j], যদি (x1-x2)^2 + (y1-y2)^2 <= k^2 হয়, adj[i].append(j), adj[j].append(i)
- seen := সেট, ans := 0
- i = 0 থেকে n-1: যদি i seen-এ না থাকে, ans++, 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
আউটপুট
2
