P5425. 语义邻域可达

场次：2026年9月11日 · 来源：CodeFun2000 P5425

题目描述

文档检索系统需要判断片段是否相关。本题将每个文档片段视为平面上的一个点。为提高检索效率，要判定两个片段是否属于同一语义簇：若它们密度相连，则认为语义相近。

概念说明

给定一组点，以及两个参数：邻域半径 $\varepsilon$ 、最小点数 $MinPts$ 。

$\varepsilon$ -邻域：点 $p$ 的 $\varepsilon$ -邻域是所有到 $p$ 的距离不超过 $\varepsilon$ 的点（含 $p$ 自身）。距离取欧氏距离 $dist(p,q)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
核心点：若点 $p$ 的 $\varepsilon$ -邻域内至少有 $MinPts$ 个点，则 $p$ 是核心点。
密度相连：点 $p$ 与点 $q$ 密度相连，当且仅当存在核心点 $o$ ，从 $o$ 出发能分别沿着核心点的“路径”走到 $p$ 和 $q$ ，路径上的每一步，都必须从一个核心点走到其 $\varepsilon$ -邻域内的某个点。

几个直接推论：

同一簇内的点彼此密度相连
噪声点（未落入任何核心点的 $\varepsilon$ -邻域）不与任何点密度相连
两个边界点（位于某核心点邻域内、自身却不是核心点）若被同一个核心点覆盖，则密度相连

输入格式

第一行四个数： $N$ 、 $M$ 、 $\varepsilon$ 、 $MinPts$

$N$ ：点的数量
$M$ ：询问数量
$\varepsilon$ ：邻域半径
$MinPts$ ：成为核心点所需的最少邻域点数

接下来 $N$ 行：每行两个浮点数 $x_i$ 、 $y_i$ ，按顺序给出编号为 $0$ 到 $N-1$ 的点的坐标。

接下来 $M$ 行：每行两个整数 $a$ 、 $b$ ，询问点 $a$ 与点 $b$ 是否密度相连。

数据范围

$1 \le N,M \le 1000$
$0 < \varepsilon \le 1000$
$2 \le MinPts \le N$
$-10000 \le$ 坐标值 $\le 10000$

输出格式

共 $M$ 行，每行一个整数：

$1$ 表示密度相连
$0$ 表示不密度相连

提示

提示：可按密度聚类 / 密度可达来做判定。

示例

示例 1

输入：

输出：

说明：

$\varepsilon=2.0$ ， $MinPts=3$ 。

点 $0,1,2$ 两两距离分别为 $1.2$ 、 $\sqrt{1.16}\approx 1.077$ 、 $\sqrt{1.64}\approx 1.281$ ，均不超过 $2.0$ ，每个点的邻域大小都是 $3$ ，因此都是核心点，彼此密度相连。

点 $3$ 与点 $4$ 相距 $\sqrt{0.41}\approx 0.640\le 2.0$ ，但各自邻域只有 $2$ 个点，不是核心点，也没有核心点能走到它们，因此是噪声点，彼此不密度相连。

点 $5$ 邻域只有自身，同样是噪声点。

示例 2

输入：

输出：

说明：

$\varepsilon=2.0$ ， $MinPts=3$ 。

点 $0,1,2$ 两两距离分别为 $1.5$ 、 $\sqrt{2.05}\approx 1.432$ 、 $\sqrt{3.4}\approx 1.844$ ，均为核心点。点 $3$ 到点 $1$ 的距离为 $\sqrt{2.93}\approx 1.712$ ，落入点 $1$ 的邻域，但自身邻域只有 $2$ 个点，是边界点；从核心点 $1$ 可以走到点 $0$ 与点 $3$ ，故 $0$ 与 $3$ 密度相连。

点 $4,5,6$ 两两距离分别为 $\sqrt{0.4}\approx 0.632$ 、 $\sqrt{2.34}\approx 1.529$ 、 $\sqrt{1.78}\approx 1.334$ ，都是核心点，形成一个独立的簇。

点 $3$ 与点 $4$ 分属不同簇，不密度相连。点 $7$ 是噪声点。

解题思路

第一步：理解问题本质

题目描述的是 DBSCAN 聚类里的三个概念，先把它们翻译成“图”的语言。

$\varepsilon$ -邻域：点 $p$ 与点 $q$ 之间连一条无向边，当且仅当 $dist(p,q)\le\varepsilon$ 。注意题目明确写了“含 $p$ 自身”，所以每个点至少有一条指向自己的“自环”，邻域大小至少为 $1$ 。
核心点：邻域大小 $\ge MinPts$ 的点。它像一个“枢纽”，可以继续向外接力。
密度相连：存在一个核心点 $o$ ，从 $o$ 出发能分别走到 $p$ 和 $q$ ，且每一步都必须从一个核心点走到它邻域内的某个点。

第 3 条里最关键的是“从一个核心点出发”这半句。它意味着：

只有核心点能当中转站，路径可以一个核心点接一个核心点地传下去；
边界点（自己不是核心、但落在某个核心点邻域里）只能当终点，走到它就停了；
噪声点既不是中转站，也不在任何核心点的终点集合里，所以它和谁都不相连 —— 包括它自己。

于是问题变成：

对每个核心连通块（互相能接力的核心点集合），把“块里所有核心点的邻域”并起来，得到一个可达点集。询问 $a,b$ 时，只要存在某个块的可达点集同时包含 $a$ 和 $b$ ，答案就是 $1$ 。

第二步：暴力解法

最直接的做法是：对每组询问 $(a,b)$ ，枚举每一个核心点 $o$ ，从 $o$ 出发沿核心点做一次搜索，看 $a$ 、 $b$ 是否都在“走到的核心点的邻域并集”里。

def answer(a, b):
    for o in range(n):
        if not core[o]:
            continue
        # 从核心点 o 出发，沿核心点扩散；每到一个核心点，
        # 就把它邻域里的点全部收进 reachable
        seen = {o}
        stack = [o]
        reachable = set(neighbors[o])
        while stack:
            u = stack.pop()
            for v in neighbors[u]:
                # 只有核心点才能继续接力
                if core[v] and v not in seen:
                    seen.add(v)
                    reachable |= neighbors[v]
                    stack.append(v)
        if a in reachable and b in reachable:
            return 1
    return 0

正确性没问题，但每次询问都要重新搜一遍核心点图：单次 $O(N^2)$ ， $M$ 次就是 $O(MN^2)$ 。 $N=M=1000$ 时约 $10^9$ 次操作，太慢。

而且不同询问之间做了大量重复工作：核心点之间的连通关系与询问无关，只需要预处理一次。

第三步：优化解法——用并查集把核心点粘起来

把“核心点”看成一张新图的结点：两个核心点距离不超过 $\varepsilon$ 就连边。这张图的一个连通分量，就是题目里“可以互相接力”的核心点集合，称为核心连通块。

连通分量可以用并查集维护：枚举所有点对 $(i,j)$ ，若两者都是核心点且距离 $\le\varepsilon$ ，就合并它们。

建边需要比较 $O(N^2)$ 对点；
并查集每次合并均摊 $O(\alpha(N))$ ，几乎等于常数。

这样“谁能到达谁”的问题就变成了“谁和谁在同一个块里”，例如询问 $(0,2)$ 时两点都是核心点、块编号相同，答案就是 $1$ 。

第四步：最优解法——每个点记录“能挂到哪些块”

只剩最后一个细节：边界点该挂在哪个块上？

核心点：挂在自己所在的块；
边界点：挂到“覆盖它的那些核心点”所在的块；
噪声点：一个块都挂不上，记空集合。

然后询问 $a,b$ 时，比较两边的块集合有没有交集即可：有交集，说明存在一个核心点 $o$ 能同时走到 $a$ 和 $b$ ，正是题目定义的密度相连。

这里必须用集合，不能只记一个块编号。原因是：一个边界点可能同时落在两个互不相连的簇的核心点邻域里。

例如下面这样的布局（ $\varepsilon=5$ 、 $MinPts=4$ ）：

   点1 (0,4)          点4 (10,4)

   点0 (0,0) ---- 点6 (5,0) ---- 点3 (10,0)

   点2 (0,-4)         点5 (10,-4)

点 $0$ 的邻域是 $\{0,1,2,6\}$ ，大小 $4$ ，是核心点；点 $3$ 同理，也是核心点；
点 $6$ 的邻域只有 $\{6,0,3\}$ ，大小 $3<4$ ，只是边界点；
点 $6$ 同时落在核心点 $0$ 和核心点 $3$ 的邻域里，所以它和左右两个簇都密度相连；
但点 $0$ 与点 $3$ 之间并不密度相连：路径若要从 $0$ 走到 $3$ ，中间必须经过点 $6$ ，而点 $6$ 不是核心点，不能继续接力。

如果实现时图省事，把“核心点与它邻域内所有点”直接 union，就会把点 $6$ 当成桥梁，把左右两个簇错误地合并， $0$ 与 $3$ 会被判成 $1$ 。这正是本题最容易踩的坑。

整个流程的复杂度是 $O(N^2\alpha(N)+M)$ ， $N=1000$ 时约 $10^6$ 次距离比较，非常轻松。

完整代码实现

"""
P5425. 语义邻域可达 - DBSCAN 密度相连判定
"""

import sys


def solve():
    """读入点集与询问，按 DBSCAN 的定义逐条回答是否密度相连。"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    eps = float(next(it))
    min_pts = int(next(it))

    xs = [0.0] * n
    ys = [0.0] * n
    for i in range(n):
        xs[i] = float(next(it))
        ys[i] = float(next(it))

    queries = [(int(next(it)), int(next(it))) for _ in range(m)]

    # 用平方距离比较，省掉 N^2 次开方；末尾的极小容差让“恰好等于 eps”
    # 的点不被浮点误差挡在门外（如 eps = 1.5 时 (0,0) 到 (1.2,0.9)）。
    eps2 = eps * eps * (1.0 + 1e-9)

    # ---------- 第一遍：数每个点 eps-邻域内有多少个点（含自身） ----------
    counts = [1] * n
    for i in range(n):
        xi = xs[i]
        yi = ys[i]
        cnt = counts[i]
        for j in range(i + 1, n):
            dx = xs[j] - xi
            dy = ys[j] - yi
            if dx * dx + dy * dy <= eps2:
                # 邻域关系对称，一次比较同时给两边计数
                cnt += 1
                counts[j] += 1
        counts[i] = cnt

    core = [cnt >= min_pts for cnt in counts]

    # ---------- 并查集：合并互相连通的核心点 ----------
    parent = list(range(n))
    size = [1] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]

    # 只在核心点之间连边：边界点不能当中转站，
    # 否则“被两个簇同时覆盖的边界点”会把两个无关的簇粘在一起。
    for i in range(n):
        if not core[i]:
            continue
        xi = xs[i]
        yi = ys[i]
        for j in range(i + 1, n):
            if not core[j]:
                continue
            dx = xs[j] - xi
            dy = ys[j] - yi
            if dx * dx + dy * dy <= eps2:
                union(i, j)

    # ---------- 第二遍：算出每个点能挂到哪些核心连通块 ----------
    groups = [None] * n
    for i in range(n):
        if core[i]:
            groups[i] = {find(i)}

    for i in range(n):
        if core[i]:
            continue
        found = set()
        xi = xs[i]
        yi = ys[i]
        for j in range(n):
            if not core[j]:
                continue
            dx = xs[j] - xi
            dy = ys[j] - yi
            if dx * dx + dy * dy <= eps2:
                found.add(find(j))
        # 噪声点的 found 为空集：它不与任何点密度相连（包括它自己）
        groups[i] = found

    out = []
    for a, b in queries:
        # 两个集合有交集 <=> 存在一个核心点能同时走到 a 和 b
        out.append("1" if groups[a] & groups[b] else "0")

    sys.stdout.write("\n".join(out))
    if out:
        sys.stdout.write("\n")


if __name__ == "__main__":
    solve()

NumPy 版本

以下版本使用 NumPy。只有在评测环境允许第三方库时才能提交；CodeFun2000 的普通 Python 环境不一定安装 NumPy。

import sys

import numpy as np


def solve():
    """按 DBSCAN 的定义判定两两是否密度相连，距离矩阵与可达矩阵都用 NumPy 算。"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    m = int(data[1])
    eps = float(data[2])
    min_pts = int(data[3])

    coords = np.fromiter(map(float, data[4:4 + 2 * n]),
                         dtype=np.float64, count=2 * n)
    points = coords.reshape(n, 2)

    cursor = 4 + 2 * n
    queries = np.fromiter(map(int, data[cursor:cursor + 2 * m]),
                          dtype=np.int64, count=2 * m).reshape(m, 2)

    # 平方距离比较，省掉 N^2 次开方；末尾的极小相对容差让“恰好等于 eps”
    # 的点不被浮点误差挡在门外（如 eps = 1.5 时 (0,0) 到 (1.2,0.9)）。
    eps2 = eps * eps * (1.0 + 1e-9)

    # 两两距离矩阵：(n,1,2) - (1,n,2) 广播出所有点对的坐标差，再平方求和。
    # 用坐标差而不是 |x|^2+|y|^2-2x·y，避免大坐标相减时的抵消误差。
    diff = points[:, None, :] - points[None, :, :]
    dist2 = (diff * diff).sum(axis=-1)

    # adj[i][j] 为真表示 j 落在 i 的 eps-邻域内（含 i 自己，对角线恒为真）
    adj = dist2 <= eps2

    # 邻域大小含自身，所以 counts 直接就是 adj 的行和
    counts = adj.sum(axis=1)
    core = counts >= min_pts

    # ---------- 核心点诱导子图的连通分量（并查集） ----------
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # 路径压缩
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra

    core_idx = np.nonzero(core)[0]
    # 核心点之间的边只取严格上三角，避免同一对点被处理两次
    core_adj = adj[np.ix_(core_idx, core_idx)]
    rows, cols = np.nonzero(np.triu(core_adj, k=1))
    for a, b in zip(core_idx[rows].tolist(), core_idx[cols].tolist()):
        union(a, b)

    # ---------- 每个核心连通块的可达点集 ----------
    qa, qb = queries[:, 0], queries[:, 1]

    if core_idx.size == 0:
        # 一个核心点都没有：所有点都是噪声点，必然不密度相连（含自询）
        answer = np.zeros(m, dtype=bool)
    else:
        roots = np.array([find(i) for i in range(n)])
        comp_of_core = roots[core_idx]

        # 把核心点按所属块排在一起，再用 bitwise_or.reduceat 一次性把同一块的
        # 邻域并起来：reach[k] 就是第 k 个核心连通块能走到的所有点。
        order = np.argsort(comp_of_core, kind="stable")
        comp_sorted = comp_of_core[order]
        starts = np.flatnonzero(np.r_[True, comp_sorted[1:] != comp_sorted[:-1]])
        reach = np.bitwise_or.reduceat(adj[core_idx[order]], starts, axis=0)

        # ---------- 回答询问 ----------
        # 两边块集合有交集 <=> 存在一个核心点能同时走到 a 和 b。
        # 噪声点不在任何块的可达点集里，所以自询也输出 0。
        answer = (reach[:, qa] & reach[:, qb]).any(axis=0)

    out = ["1" if flag else "0" for flag in answer.tolist()]
    sys.stdout.write("\n".join(out))
    if out:
        sys.stdout.write("\n")


if __name__ == "__main__":
    solve()

示例推演

样例 1

输入 $6$ 个点， $\varepsilon=2.0$ 、 $MinPts=3$ 。先算出每个点的邻域：

点	坐标	邻域内的点	邻域大小	是否核心点
0	$(0,0)$	$\{0,1,2\}$	3	是
1	$(1.2,0)$	$\{0,1,2\}$	3	是
2	$(0.4,1)$	$\{0,1,2\}$	3	是
3	$(12,0)$	$\{3,4\}$	2	否
4	$(12.5,0.4)$	$\{3,4\}$	2	否
5	$(6,6)$	$\{5\}$	1	否

点 $0,1,2$ 之间的距离分别是 $1.2$ 、 $\sqrt{1.16}\approx1.077$ 、 $\sqrt{1.64}\approx1.281$ ，都不超过 $2.0$ ，所以三点互相连边，合并成一个核心连通块，记作 $A$ 。

点 $3$ 与点 $4$ 虽然相距 $\sqrt{0.41}\approx0.640\le2.0$ ，但两点都不是核心点，不能互相接力，也都不在任何核心点的邻域里，因此都是噪声点。

于是：

点	能挂到的核心连通块
0、1、2	$\{A\}$
3、4、5	$\varnothing$

四组询问：

$0,2$ ： $\{A\}\cap\{A\}=\{A\}$ ，输出 $1$ ；
$0,3$ ： $\{A\}\cap\varnothing=\varnothing$ ，输出 $0$ ；
$3,4$ ： $\varnothing\cap\varnothing=\varnothing$ ，输出 $0$ （两个噪声点彼此也不相连）；
$1,5$ ： $\{A\}\cap\varnothing=\varnothing$ ，输出 $0$ 。

样例 2

$\varepsilon=2.0$ 、 $MinPts=3$ ：

点	坐标	邻域内的点	邻域大小	是否核心点
0	$(0,0)$	$\{0,1,2\}$	3	是
1	$(1.5,0)$	$\{0,1,2,3\}$	4	是
2	$(0.3,1.4)$	$\{0,1,2\}$	3	是
3	$(3.2,0.2)$	$\{1,3\}$	2	否
4	$(8,8)$	$\{4,5,6\}$	3	是
5	$(8.6,8.2)$	$\{4,5,6\}$	3	是
6	$(8.3,9.5)$	$\{4,5,6\}$	3	是
7	$(0,8)$	$\{7\}$	1	否

点 $1$ 到点 $3$ 的距离是 $\sqrt{1.7^2+0.2^2}=\sqrt{2.93}\approx1.712\le2.0$ ，所以点 $3$ 落在核心点 $1$ 的邻域里，是边界点，挂到核心连通块 $A=\{0,1,2\}$ 上。

点 $4,5,6$ 两两距离约 $0.632$ 、 $1.529$ 、 $1.334$ ，全部 $\le2.0$ ，形成另一个核心连通块 $B$ 。

点	能挂到的核心连通块
0、1、2、3	$\{A\}$
4、5、6	$\{B\}$
7	$\varnothing$

四组询问：

$0,2$ ：同属 $A$ ，输出 $1$ ；
$0,3$ ： $0$ 是核心点、 $3$ 是 $A$ 的边界点，都在 $A$ 的可达点集里，输出 $1$ ；
$4,5$ ：同属 $B$ ，输出 $1$ ；
$3,4$ ： $3$ 只在 $A$ 、 $4$ 只在 $B$ ，交集为空，输出 $0$ 。

复杂度分析

解法	时间复杂度	空间复杂度	说明
逐询问 BFS	$O(MN^2)$	$O(N^2)$	每组询问都重新搜一遍核心点图， $N=M=1000$ 时约 $10^9$ 次操作
并查集合并全部邻域	$O(N^2\alpha(N)+M)$	$O(N)$	把边界点也 `union` 进去，会把共享边界点连接的两个簇错误合并
并查集 + 块集合（本题）	$O(N^2\alpha(N)+M)$	$O(N+M)$	预处理一次，回答所有询问；边界点允许挂多个块

两遍 $O(N^2)$ 的扫描在 $N=1000$ 时约 $1.5\times10^6$ 次距离计算，Python 中运行时间远小于 $0.2$ 秒。

易错点总结

1. 邻域必须包含点自身

题目写的是“距离不超过 $\varepsilon$ 的点（含 $p$ 自身）”。所以邻域大小的计数要从 $1$ 开始，counts 全部初始化为 $1$ 。忘记这一点会让所有点的邻域大小少 $1$ ， $MinPts$ 恰好等于真实邻域大小的点会被误判成边界点。

2. 核心点的判据是 $\ge MinPts$

注意是“至少 $MinPts$ 个点”，用 >= 而不是 >。

3. 边界点不能当中转站

这是本题与“无脑并查集”的分水岭。路径的每一步都必须从核心点出发，所以：

建图时只在核心点之间连边；
边界点只作为终点被记录，不能继续向外扩散。

否则“被两个簇同时覆盖的边界点”会把两个本来无关的簇连成一个，回答 $0$ 的询问会变成 $1$ 。

4. 一个点可能挂在多个核心连通块上

边界点可能同时落在两个簇的核心点邻域里。用集合记录“能挂到哪些块”，询问时判断交集是否非空；只记一个块编号（或直接并查集合并）都会丢信息。

5. 噪声点与它自己也不相连

噪声点不在任何核心点的邻域里，没有任何核心点能“走到”它，所以询问 $(p,p)$ 在 $p$ 是噪声点时应输出 $0$ ，而不是想当然地输出 $1$ 。

6. 用平方距离比较，并给边界留一点容差

判断 $dist\le\varepsilon$ 时比较 $dx^2+dy^2\le\varepsilon^2$ 即可，不需要开方。但浮点数下 $1.2^2+0.9^2$ 可能算成 $2.2500000000000004$ ，而 $\varepsilon^2=2.25$ ，本该“恰好相等”的点会被判成邻域外。乘上 1.0 + 1e-9 这样的相对容差可以避免这类误判。

7. 输出的是整数 $0/1$

每行一个整数，不要输出 YES / NO / True / False。

扩展思考

如果题目要求输出每个点的簇编号：那就回到了 DBSCAN 的经典歧义 —— 边界点被多个簇覆盖时该归谁？常见做法是“先到先得”，即按扫描顺序分配给第一个声明它的簇。本题只问“是否相连”，用集合表达天然没有歧义。
如果 $N$ 达到 $10^5$ ： $O(N^2)$ 建边不可行，需要用空间索引（网格划分、k-d 树）只枚举“可能落在 $\varepsilon$ 内”的点对，把建边降到接近 $O(N\log N)$ 。
如果 $\varepsilon$ 是动态查询参数：预处理帮不上忙，只能每次重新建图，此时单次询问的暴力做法反而更合适。
与“连通分量”的区别：普通图的连通分量只看有没有路径，而这里限制了路径中间的结点必须是核心点。也就是说，本题的“连通”是在核心点诱导子图上定义的，边界点只享受“终点”待遇。

题目描述​

概念说明​

输入格式​

数据范围​

输出格式​

提示​

示例​

示例 1​

示例 2​

解题思路​

第一步：理解问题本质​

第二步：暴力解法​

第三步：优化解法——用并查集把核心点粘起来​

第四步：最优解法——每个点记录“能挂到哪些块”​

完整代码实现​

NumPy 版本​

示例推演​

样例 1​

样例 2​

复杂度分析​

易错点总结​

1. 邻域必须包含点自身​

2. 核心点的判据是 ≥MinPts\ge MinPts≥MinPts​

3. 边界点不能当中转站​

4. 一个点可能挂在多个核心连通块上​

5. 噪声点与它自己也不相连​

6. 用平方距离比较，并给边界留一点容差​

7. 输出的是整数 0/10/10/1​

扩展思考​

相关题目​