Chương trình phân nhóm tập điểm thành K nhóm khác nhau trong Python

Cho danh sách điểm và số . Hai điểm cùng nhóm nếu khoảng cách Euclid ≤ k. Tìm số nhóm không giao nhau (connected components).

Ví dụ: , → 2 nhóm.

Giải thuật (Xây đồ thị + DFS tìm thành phần liên thông)

1. Xây danh sách kề : với mỗi cặp điểm , nếu khoảng cách bình phương ≤ thì thêm cạnh hai chiều.
2. DFS/BFS tìm số thành phần liên thông trên đồ thị vô hướng.
3. Trả về số thành phần.

Ví dụ minh họa

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))  # Output: 2

Đầu vào

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

Đầu ra

2