2026-07-10：添加一个点后可激活的最大点数。用go语言，给定一个二维整数点集合 points，points[i]=[xi,yi] 表示第 i 个点的坐标，且所有

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；
二分图中同一个连通分量里，所有行、列互相连通。只要连通分量内任意一行/一列被触发，该分量内所有原始点都会被激活。

2. 添加新点(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，保证行列节点值域完全不重叠，不会冲突。

二、代码完整分步流程（分4大阶段，结合示例[[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)都会直接返回自身。

阶段2：遍历所有原始点，合并对应行、列节点（构建连通关系）

循环每一个坐标点p=[px,py]：

1. 找到行节点px的根：rx = find(px)

2. 找到列节点py+offset的根：ry = find(py + offset)

3. 将rx的父节点赋值为ry，完成两个集合合并（Union操作）。

示例分步合并演示（输入3个点）

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个连通块。

阶段3：统计每个连通块包含的原始点数量（size map）

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数据。

2. 总额外空间复杂度

占用三块哈希表空间：

1. fa：存储所有出现过的行、列节点，最多2n个key；

2. size：存储每个连通块根节点，最多n个key；
总额外空间复杂度：O(n)。

Go完整代码如下：

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助力您的未来发展。