Kimi LeetCode 3873. 添加一个点后可激活的最大点数 Java实现

下面是 LeetCode 3873. 添加一个点后可激活的最大点数 的 Java 实现。

解题思路

这道题的核心是并查集（Union-Find） + 二分图建模：

1. 模型转化：将每个点 `(x, y)` 看作连接 行节点 `x` 和 列节点 `y` 的一条边。这样，同 x 或同 y 的点会在同一个连通分量中。

2. 坐标区分：由于 x 和 y 的取值范围都是 `[-1e9, 1e9]`，直接合并会冲突。给 y 加上一个足够大的偏移量 `offset = 3e9`，使行列节点值域完全不重叠。

3. 添加新点的作用：新点 `(a, b)` 相当于连接行 `a` 和列 `b`。如果 `a` 和 `b` 分别属于两个不同的连通块，就能将这两个块合并激活。因此答案 = 最大两个连通块的大小之和 + 1（+1 是新点自身）。

Java 代码

```java
import java.util.*;

class UnionFind {
    Map<Long, Long> p = new HashMap<>();
    Map<Long, Integer> size = new HashMap<>();

    long find(long x) {
        if (!p.containsKey(x)) {
            p.put(x, x);
            size.put(x, 1);
        }
        if (p.get(x) != x) {
            p.put(x, find(p.get(x)));
        }
        return p.get(x);
    }

    boolean union(long a, long b) {
        long pa = find(a), pb = find(b);
        if (pa == pb) {
            return false;
        }
        int sa = size.get(pa), sb = size.get(pb);
        if (sa > sb) {
            p.put(pb, pa);
            size.put(pa, sa + sb);
        } else {
            p.put(pa, pb);
            size.put(pb, sa + sb);
        }
        return true;
    }
}

class Solution {
    public int maxActivated(int[][] points) {
        UnionFind uf = new UnionFind();
        long m = (long) 3e9;

        // 合并每个点的 x 和 y+offset
        for (int[] p : points) {
            uf.union(p[0], p[1] + m);
        }

        // 统计每个连通块包含的原始点数量
        Map<Long, Integer> cnt = new HashMap<>();
        for (int[] p : points) {
            cnt.merge(uf.find(p[0]), 1, Integer::sum);
        }

        // 找最大和次大的连通块
        int mx1 = 0, mx2 = 0;
        for (int x : cnt.values()) {
            if (mx1 < x) {
                mx2 = mx1;
                mx1 = x;
            } else if (mx2 < x) {
                mx2 = x;
            }
        }

        return mx1 + mx2 + 1;
    }
}
```

复杂度分析

– 时间复杂度：`O(n · α(n))`，其中 `α` 是阿克曼函数的反函数，近似常数。并查集的 `find` 和 `union` 均摊复杂度极低。
– 空间复杂度：`O(n)`，存储并查集的父节点和大小信息。