解题思路
核心思路:密度相连只允许从核心点迈向其 ε-邻域。欧氏距离对称,因此两个核心点只要互相落在邻域内就可以双向走。先找出所有核心点,再在核心点之间按邻域关系做并查集,每个核心连通块覆盖「块内所有核心点的邻域并」。两点密度相连当且仅当它们共同出现在某一块的覆盖集合里。噪声点不属于任何覆盖,与任何点(含自身)都不相连。边界点可同时落入多块覆盖,询问时取集合交集即可。
实现方法:用平方距离判断邻域,避免开方。N≤1000,两两枚举即可。核心点并查集之后,把每个核心的邻域点记到该块的覆盖里,再回答 M 组询问。
复杂度分析
时间复杂度:O(N2+M)。邻域枚举 O(N2),并查集与覆盖收集 O(N2α(N)),询问按所属块数量均摊不超过 O(N+M)。