解题思路

DBSCAN 基于“密度”成簇：对每个点找 eps 邻域（欧氏距离 ≤ eps 的点集合），若邻域样本数 ≥ min_samples，该点为核心点；从未访问的核心点出发，用 BFS/DFS 扩展，将其邻域内的点并入当前簇；若被并入的点本身也是核心点，则继续把它的邻域加入队列，直到不再扩展。最终没有被任何簇吸纳的点即为噪声点。

实现细节：

1. 计算并缓存所有点的邻居列表（两两距离判断，含自身）；维度不写死，自动支持二维或三维输入。
2. core[i] = (len(neighbors[i]) >= min_samples) 判定核心点。
3. 逐点扫描：若是未访问的核心点，创建新簇并用队列扩展；扩展时把邻居标成当前簇，遇到核心点则把它的邻居继续入队。
4. 统计得到的簇个数与仍为 -1 的样本数（噪声点）。

复杂度分析

• 设样本数为 n，维度 d∈{2,3}。
• 预计算邻居：O(n^2 * d)；扩展遍历整体 O(n^2)。
• 总时间复杂度 O(n^2 * d)；空间复杂度（邻接表）O(n^2)，标记与标签 O(n)。在题目给定规模下可接受。

代码实现

Python

import sys
from collections import deque
from ast import literal_eval

def dist2(a, b):
    # 欧氏距离平方，维度自适应（2D/3D均可）
    return sum((ai - bi) ** 2 for ai, bi in zip(a, b))

def dbscan(points, eps, min_samples):
    n = len(points)
    if n == 0:
        return 0, 0
    eps2 = eps * eps

    # 预计算邻居（含自身），阈值用 <=
    neighbors = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if dist2(points[i], points[j]) <= eps2:
                neighbors[i].append(j)

    core = [len(neighbors[i]) >= min_samples for i in range(n)]
    labels = [-1] * n
    visited = [False] * n
    cluster_id = 0

    for i in range(n):
        if visited[i]:
            continue
        visited[i] = True
        if not core[i]:
            continue

        labels[i] = cluster_id
        q = deque(neighbors[i])  # 从核心点的邻居开始扩展
        in_q = [False] * n
        for nb in neighbors[i]:
            in_q[nb] = True

        while q:
            j = q.popleft()
            if labels[j] == -1:
                labels[j] = cluster_id
            if not visited[j]:
                visited[j] = True
                if core[j]:
                    for nb in neighbors[j]:
                        if not in_q[nb]:
                            q.append(nb)
                            in_q[nb] = True
        cluster_id += 1

    noise = sum(1 for v in labels if v == -1)
    return cluster_id, noise

def main():
    data = sys.stdin.read().strip().splitlines()
    if not data:
        return
    a, b, c = data[0].split()
    eps = float(a)
    min_samples = int(b)
    x = int(c)

    points = [list(map(float,data[i].split())) for i in range(1, 1 + x)]
    clusters, noise = dbscan(points, eps, min_samples)
    print(f"{clusters} {noise}")

if __name__ == "__main__":
    main()

Java

import java.io.BufferedInputStream;
import java.util.*;

public class Main {
    static double dist2(double[] a, double[] b) {
        double s = 0.0;
        for (int i = 0; i < a.length; i++) {
            double d = a[i] - b[i];
            s += d * d;
        }
        return s;
    }

    static int[] dbscan(List<double[]> points, double eps, int minSamples) {
        int n = points.size();
        if (n == 0) return new int[]{0, 0};
        double eps2 = eps * eps;

        // 邻居列表（含自身）
        List<List<Integer>> neighbors = new ArrayList<>();
        for (int i = 0; i < n; i++) neighbors.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            double[] pi = points.get(i);
            for (int j = 0; j < n; j++) {
                if (dist2(pi, points.get(j)) <= eps2) {
                    neighbors.get(i).add(j);
                }
            }
        }

        boolean[] core = new boolean[n];
        for (int i = 0; i < n; i++) core[i] = neighbors.get(i).size() >= minSamples;

        int[] labels = new int[n];
        Arrays.fill(labels, -1);
        boolean[] visited = new boolean[n];
        int clusterId = 0;

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            if (!core[i]) continue;

            labels[i] = clusterId;
            ArrayDeque<Integer> q = new ArrayDeque<>();
            boolean[] inQ = new boolean[n];
            for (int nb : neighbors.get(i)) {
                q.add(nb); inQ[nb] = true;
            }
            while (!q.isEmpty()) {
                int j = q.poll();
                if (labels[j] == -1) labels[j] = clusterId;
                if (!visited[j]) {
                    visited[j] = true;
                    if (core[j]) {
                        for (int nb : neighbors.get(j)) {
                            if (!inQ[nb]) { q.add(nb); inQ[nb] = true; }
                        }
                    }
                }
            }
            clusterId++;
        }

        int noise = 0;
        for (int v : labels) if (v == -1) noise++;
        return new int[]{clusterId, noise};
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new BufferedInputStream(System.in), "UTF-8");
        if (!sc.hasNext()) { sc.close(); return; }
        double eps = sc.nextDouble();
        int minSamples = sc.nextInt();
        int x = sc.nextInt();
        sc.nextLine();

        List<double[]> points = new ArrayList<>();
        for (int i = 0; i < x; i++) {
            String line = sc.nextLine().trim();
            if (line.isEmpty()) { i--; continue; }
            String[] sp = line.split("\\s+"); // 空格分隔，2D/3D皆可
            double[] row = new double[sp.length];
            for (int k = 0; k < sp.length; k++) row[k] = Double.parseDouble(sp[k]);
            points.add(row);
        }
        sc.close();

        int[] ans = dbscan(points, eps, minSamples);
        System.out.println(ans[0] + " " + ans[1]);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

double dist2(const vector<double>& a, const vector<double>& b) {
    double s = 0.0;
    for (size_t i = 0; i < a.size(); ++i) {
        double d = a[i] - b[i];
        s += d * d;
    }
    return s;
}

pair<int,int> dbscan(const vector<vector<double>>& points, double eps, int min_samples) {
    int n = (int)points.size();
    if (n == 0) return {0, 0};
    double eps2 = eps * eps;

    vector<vector<int>> neighbors(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist2(points[i], points[j]) <= eps2) {
                neighbors[i].push_back(j);
            }
        }
    }

    vector<char> core(n, false);
    for (int i = 0; i < n; ++i) {
        if ((int)neighbors[i].size() >= min_samples) core[i] = true;
    }

    vector<int> labels(n, -1);
    vector<char> visited(n, false);
    int cluster_id = 0;

    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        if (!core[i]) continue;

        labels[i] = cluster_id;
        deque<int> q;
        vector<char> in_q(n, false);
        for (int nb : neighbors[i]) { q.push_back(nb); in_q[nb] = true; }

        while (!q.empty()) {
            int j = q.front(); q.pop_front();
            if (labels[j] == -1) labels[j] = cluster_id;
            if (!visited[j]) {
                visited[j] = true;
                if (core[j]) {
                    for (int nb : neighbors[j]) {
                        if (!in_q[nb]) { q.push_back(nb); in_q[nb] = true; }
                    }
                }
            }
        }
        ++cluster_id;
    }

    int noise = 0;
    for (int v : labels) if (v == -1) ++noise;
    return {cluster_id, noise};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    double eps; int min_samples, x;
    if (!(cin >> eps >> min_samples >> x)) return 0;
    string dummy; getline(cin, dummy);

    vector<vector<double>> points;
    points.reserve(x);
    for (int i = 0; i < x; ++i) {
        string line; getline(cin, line);
        if (line.empty()) { --i; continue; }
        stringstream ss(line);
        vector<double> row; double v;
        while (ss >> v) row.push_back(v); // 2D/3D兼容
        points.push_back(row);
    }

    auto res = dbscan(points, eps, min_samples);
    cout << res.first << " " << res.second << "\n";
    return 0;
}

题目内容

$DBSCAN$（$Density-Based$ $Spatial$ $Clustering$ $of$ $Applications$ $with$ $Noise$）是一种基于密度的聚类算法。它能够识别出噪声点，发现任意形状的簇，其核心概念包括：

1. eps-邻域：样本点 $P$ 与 点 $Q$ 的距离小于 $eps$ 的所有样本点的集合，即点 $P$ 周围以 $eps$ 为半径内所有样本点的集合。

2. 核心点：若点 $P$ 的 $eps$ 邻域内的样本点数量大于 $min\_samples$ 的阈值，则称点 $P$ 为核心点。

3. 直接密度可达：若点 $P$ 是核心点，且点 $Q$ 处于点 $P$ 的 $eps$ 邻域内，则称点 $Q$ 由点 $P$ 直接密度可达。

4. 密度可达：若有一串点 $P_1, P_2, ..., P_n$，对于任意 $i$，$P_{i+1}$ 可由 $P_i$ 直接密度可达，则称点 $P_n$ 可由点 $P_1$ 密度可达。

5. 密度相连：若存在点 $O$ ，使得点 $P$ 和点 $Q$ 都可由 $O$ 密度可达，则称点 $P$ 和点 $Q$ 是密度相连的。

6. 簇：对于任意的点 $P$ 和点 $Q$ ，若点 $P$ 属于某个簇，且点 $Q$ 由点 $P$ 密度可达，则点 $Q$ 也属于这个簇。同理，由点 $Q$ 密度可达的点也属于这个簇。即同一簇内的点，是密度相连的。

7. 噪声点：不属于样本集内任何簇的样本点。

请你根据以上要求实现 $DBSCAN$ 算法，要求根据给定的数据集、$eps$ 和 $min\_samples$ 值，输出簇的个数和噪声点的个数。

输入描述

第一行输入 $3$ 个数 $eps$, $min\_samples$, $x$，以空格隔开，分别表示：

• $eps$：计算 $eps$-邻域的半径值，可为小数
• $min\_samples$：核心点的 $eps$-邻域内样本点数量阈值，整数
• $x$：数据集行数，即样本数量，整数

第二行开始为输入的样本数据，数值之间用空格隔开，共输入 $x$ 行，每行输入数值数量为 $y$，$2 \leq y \leq 3$

输出描述

输出两个值，用空格隔开，第一个值表示得到的簇的个数，第二个值表示识别到的噪声点的个数

样例1

输入

2 2 10
0 0
3 3
6 6
9 9
12 12
2 6
6 2
9 5
5 9
10 2

输出

0 10

说明

$eps$ 设为 $2$，$min\_samples$ 为 $2$，但给出的数据集中任意两个点之间的距离都大于$2$，因此即使 $min\_sample$ 设置为 $2$，也没有形成任何簇，即所有的点都是噪声，如下图：

样例2

输入

1 5 20
5.05 1.36
-8.19 -6.47
4.5 2.5
5.01 2.06
4.30 2.28
4.22 1.82
4.58 1.82
4.81 2.46
4.81 1.09
4.80 1.78
5.16 2.44
-6.92 -6.38
-6.84 -7.03
-6.70 -7.20
-6.83 -7.87
-6.47 -6.20
-6.70 -6.11
-6.90 -6.10
-6.99 -6.70
5 5

输出

2 2  

说明

样例数据集中共 $20$ 个点，给定 $eps$ 为 $1$ ， $min\_samples$ 为 $5$ ，聚类后得到两个簇： 一个在坐标系第一象限，一个在第三象限，且存在两个噪声点 $(5, 5)$ 和 $(-8.19, -6.47)$不属于任何簇，如下图：