在Python中将一组点分为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()。这需要我
如果我在里面，那么
dfs(nb)
从主要方法，请执行以下操作-
adj：=映射
n：=点的大小
对于0到n范围内的j，执行
看过：=一套新的
回答：=0
对于0到n范围内的i，执行
返回ans
p1：=分[i]
p2：=分[j]
如果p1和p2之间的欧几里得距离<k，则
在adj[i]的末尾插入j
在adj[j]的末尾插入i
对于0到j范围内的i，执行
ans：=ans+1
dfs(i)
如果我没看到，那
返回
将我插入看到
对于adj[i]中的每个nb，执行
让我们看下面的实现以更好地理解-
示例
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