2026-07-10：添加一个点后可激活的最大点数。用go语言，给定一个二维整数点集合 points，points[i]=[xi,yi] 表示第 i 个点的坐标，且所有坐标都互不相同。
当你选择“激活”某一个点后，会按照规则扩散：凡是与该点在 x 坐标相同或 y 坐标相同的其他点，也会被一起激活。只要还能通过“已激活的点”继续找到满足同 x 或同 y 的点，就会不断继续激活，直到再也找不到新的点为止。
你允许额外加入一个不在原 points 中的整数坐标点 (x,y)，然后从这个新点开始触发激活过程。
要求输出一个整数：在你选择加入的点 (x,y) 之后，最终最多能被激活的点的数量（包含这个新加入的点本身）。
1 <= points.length <= 100000。
points[i] = [xi, yi]。
-1000000000 <= xi, yi <= 1000000000。
points 中的坐标均 互不相同。
输入： points = [[1,1],[1,2],[2,2]]。
输出： 4。
解释：
添加并激活一个点，例如 (1, 3)，会导致以下激活：
(1, 3) 与 (1, 1) 和 (1, 2) 具有相同的 x = 1，因此 (1, 1) 和 (1, 2) 被激活。
(1, 2) 与 (2, 2) 具有相同的 y = 2，因此 (2, 2) 被激活。
因此，被激活的点为 (1, 3), (1, 1), (1, 2), (2, 2)，总计 4 个点。可以证明这是最大激活点数。
题目来自力扣3873。
一、题目模型转化 1. 激活规则等价图模型
每个原始点(x,y)满足：同x、同y的点会互相连通激活，该规则可建模为二分图：
• 左分区：所有横坐标
x（行节点）• 右分区：所有纵坐标
y（列节点）• 对每个原始点
(xi,yi)，连一条边xi ↔ yi；
二分图中同一个连通分量里，所有行、列互相连通。只要连通分量内任意一行/一列被触发，该分量内所有原始点都会被激活。
(a,b)的作用新增点(a,b)不在原集合中，激活它等价于：用一条虚拟边连接行节点a、列节点b，会把a所在连通块和b所在连通块合并成一个大连通块。
最终激活总数 = 块A原始点数 + 块B原始点数 + 1（新增点自身）。
最优解就是选取两个原始连通块大小之和最大的组合，再加1。
3. 坐标冲突解决：偏移量offset
x、y数值范围都是[-1e9,1e9]，直接存会出现x和y数值重复、节点混淆。
代码用常量offset=3e9区分两类节点：
• 行节点：直接存原值
x• 列节点：存储
y + offset，保证行列节点值域完全不重叠，不会冲突。
[[1,1],[1,2],[2,2]]讲解） 阶段1：初始化哈希版并查集（fa map + 递归带路径压缩find）1. 定义
fa map[int]int：key是行列节点编号，value是该节点的父节点；2. 递归
find(x)函数（路径压缩）：
• 如果
x不在fa中（首次出现），直接返回自身作为根；• 如果
x存在父节点且父节点≠自身，递归找到根，并把fa[x]直接赋值为根（路径压缩）；• 返回当前节点最终根节点。
示例初始化：fa为空，find(1)、find(1+3e9)、find(2)、find(2+3e9)都会直接返回自身。
循环每一个坐标点p=[px,py]：
1. 找到行节点
px的根：rx = find(px)2. 找到列节点
py+offset的根：ry = find(py + offset)3. 将
rx的父节点赋值为ry，完成两个集合合并（Union操作）。
1. 第一个点
[1,1]：
rx=find(1)=1，ry=find(1+3e9)=1+3e9；fa[1]=1+3e9；2. 第二个点
[1,2]：
rx=find(1) → 递归找到根1+3e9；ry=find(2+3e9)=2+3e9；fa[1+3e9]=2+3e9；3. 第三个点
[2,2]：
rx=find(2)=2；ry=find(2+3e9)=2+3e9；fa[2]=2+3e9；
最终所有行、列节点全部合并到同一个根2+3e9，全局只有1个连通块。
1. 新建
size map[int]int：key是连通块根节点，value是该块内原始点总数；2. 再次遍历全部原始点
p=[px,py]：
• 对当前点取行节点px的根
root = find(px)；• size[root]自增1，代表该连通块多1个原始坐标点。
3个点执行后，所有点的find(px)根都相同，size中唯一key对应值=3。
阶段4：取最大两个连通块大小，计算答案
1. 遍历size哈希表，记录全局最大块mx1、次大块mx2；
2. 答案公式：
mx1 + mx2 + 1
• mx1+mx2：两个连通块全部原始点；
• +1：新增的那个点本身；
3. 输出最终数值。
示例计算过程
size仅存在一个数值3：mx1=3，mx2=0；
结果=3+0+1=4，与题目样例输出完全匹配。
三、边界逻辑补充说明
1. 若原图只有1个连通块：mx2=0，新增点只连接本块，总激活=原块全部点+1；
2. 若原图有多个独立连通块：取规模前二的两块合并，能得到全局最大值；
3. 新增点
(a,b)的a、b可以不存在于原图行列，此时对应连通块大小为0，不影响计算。
设原始点数量为n，题目约束1 ≤ n ≤ 1e5
1. 总时间复杂度
1. 两次完整遍历points数组：2轮O(n)循环；
2. 每轮循环内部执行2次find操作；find带路径压缩，单次均摊复杂度
O(α(n))，α是逆阿克曼函数，n≤1e5时α(n)≤4，近似常数；3. 最后遍历size哈希表：哈希表键总数不超过2n，遍历O(n)；
总均摊时间复杂度：O(n·α(n)) ≈ O(n)，线性复杂度，可通过1e5数据。
占用三块哈希表空间：
1. fa：存储所有出现过的行、列节点，最多2n个key；
2. size：存储每个连通块根节点，最多n个key；
总额外空间复杂度：O(n)。
package main
import (
"fmt"
)
func maxActivated(points [][]int)int {
// 哈希表并查集
fa := map[int]int{}
var find func(int)int
find = func(x int)int {
fx, ok := fa[x]
if !ok {
return x
}
if fx != x {
fa[x] = find(fx)
return fa[x]
}
return x
}
const offset int = 3e9
for _, p := range points {
fa[find(p[0])] = find(p[1] + offset)
}
size := map[int]int{}
for _, p := range points {
size[find(p[0])]++ // 统计连通块的大小
}
mx1, mx2 := 0, 0
for _, sz := range size {
if sz > mx1 {
mx2 = mx1
mx1 = sz
} elseif sz > mx2 {
mx2 = sz
}
}
return mx1 + mx2 + 1
}func main() {
points := [][]int{{1, 1}, {1, 2}, {2, 2}}
result := maxActivated(points)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
def maxActivated(points: List[List[int]]) -> int:
"""
计算最大激活点数
使用并查集将相关联的点连接起来，然后找到最大的两个连通块
"""
# 并查集父节点字典
fa = {}
def find(x: int) -> int:
"""查找根节点并进行路径压缩"""
if x not in fa:
return x
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
offset = 3 * 10**9 # 偏移量，用于区分第一维和第二维
# 将每个点的两个维度值连接起来
for p in points:
# 分别获取两个维度的根节点
root1 = find(p[0])
root2 = find(p[1] + offset)
# 将两个根节点合并
fa[root1] = root2
# 统计每个连通块的大小
size = {}
for p in points:
root = find(p[0])
size[root] = size.get(root, 0) + 1
# 找出最大的两个连通块大小
mx1, mx2 = 0, 0
for sz in size.values():
if sz > mx1:
mx2 = mx1
mx1 = sz
elif sz > mx2:
mx2 = sz
# 返回最大两个连通块之和再加1
return mx1 + mx2 + 1
def main():
points = [[1, 1], [1, 2], [2, 2]]
result = maxActivated(points)
print(result)if __name__ == "__main__":
main()
C++完整代码如下：
using namespace std;/**
* 计算最大激活点数
* 使用并查集将相关联的点连接起来，然后找到最大的两个连通块
*/
int maxActivated(vector int >>& points) {
// 哈希表并查集
unordered_map< int , int > fa;
// 定义并查集的查找函数（使用递归，不用std::function）
auto find = [&](auto&& self, int x) -> int {
auto it = fa.find(x);
if (it == fa.end()) {
return x; // 如果x不在映射中，则x是根节点
}
if (it->second != x) {
// 路径压缩
fa[x] = self(self, it->second);
return fa[x];
}
return x;
};
const int offset = 3000000000 ; // 3e9，用于区分第一维和第二维
// 将每个点的两个维度值连接起来
for ( const auto& p : points) {
int root1 = find(find, p[ 0 ]);
int root2 = find(find, p[ 1 ] + offset);
fa[root1] = root2; // 合并两个根节点
}
// 统计每个连通块的大小
unordered_map< int , int > size;
for ( const auto& p : points) {
int root = find(find, p[ 0 ]);
size[root]++; // 统计连通块的大小
}
// 找出最大的两个连通块大小
int mx1 = 0 , mx2 = 0 ;
for ( const auto& kv : size) {
int sz = kv.second;
if (sz > mx1) {
mx2 = mx1;
mx1 = sz;
} else if (sz > mx2) {
mx2 = sz;
}
}
// 返回最大两个连通块之和再加1
return mx1 + mx2 + 1 ;
}
int main() {
vector int >> points = {{ 1 , 1 }, { 1 , 2 }, { 2 , 2 }};
int result = maxActivated(points);
cout << result << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴