ধরুন আমাদের কাছে পয়েন্টের একটি তালিকা এবং একটি সংখ্যা 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() সংজ্ঞায়িত করুন। এর জন্য i
লাগবে -
যদি আমি দেখতে পাই, তাহলে
-
ফেরত
-
ঢোকান আমি দেখেছি
-
adj[i]-এ প্রতিটি nb-এর জন্য, do
-
dfs(nb)
-
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন−
-
adj :=একটি মানচিত্র
-
n :=পয়েন্টের আকার
-
0 থেকে n রেঞ্জে j এর জন্য, করুন
-
আমি 0 থেকে j রেঞ্জের জন্য, করুন
-
p1 :=পয়েন্ট[i]
-
p2 :=পয়েন্ট[j]
-
যদি p1 এবং p2
-
adj[i]
এর শেষে j সন্নিবেশ করান -
adj[j]
এর শেষে i ঢোকান
-
-
-
-
দেখা হয়েছে :=একটি নতুন সেট
-
উত্তর :=0
-
0 থেকে n রেঞ্জের জন্য, করুন
-
আমি যদি না দেখি, তাহলে
-
ans :=ans + 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
