Chemical Table 题解

题目理解

我们有一个 $n \times m$ 的元素周期表，初始时已经拥有 $q$ 种元素的样品。通过核聚变反应规则：如果存在位置为 $(r_1,c_1)$、$(r_1,c_2)$、$(r_2,c_1)$ 的三种元素（其中 $r_1 \neq r_2$，$c_1 \neq c_2$），那么就可以生成位置为 $(r_2,c_2)$ 的元素。

目标是求出至少需要购买多少种额外的元素样品，才能通过核聚变反应获得所有 $n \times m$ 种元素。

问题转化

这个核聚变规则可以理解为：如果我们有一个 "L" 形的三个点（两个在同一行，两个在同一列），那么就能填上第四个点，完成一个矩形。

这实际上是一个图论问题：

• 将行和列看作图中的节点
• 每个已有的元素 $(r_i, c_i)$ 可以看作连接第 $r_i$ 行节点和第 $c_i$ 列节点的边

在这样的二分图中，如果存在一个连通分量包含 $x$ 个行节点和 $y$ 个列节点，那么通过反应我们可以得到这个子矩阵中的所有 $x \times y$ 个元素。

关键观察

考虑二分图 $G$，其中：

• 左部节点表示行（共 $n$ 个）
• 右部节点表示列（共 $m$ 个）
• 每个元素 $(r_i, c_i)$ 对应一条连接行 $r_i$ 和列 $c_i$ 的边

重要结论：如果二分图 $G$ 有 $k$ 个连通分量，那么我们需要额外购买 $k-1$ 个元素样品。

为什么？

• 每个连通分量对应一个"反应区域"
• 如果连通分量包含 $a$ 个行节点和 $b$ 个列节点，那么我们可以生成该 $a \times b$ 子矩阵中的所有元素
• 但不同连通分量之间无法直接反应
• 要连接 $k$ 个连通分量，需要 $k-1$ 条额外的边（即购买 $k-1$ 个样品）

算法实现

使用并查集来维护这个二分图的连通性：

• 初始化并查集，大小为 $n + m$（前 $n$ 个节点代表行，后 $m$ 个节点代表列）
• 对于每个元素 $(r, c)$，将节点 $r$ 和节点 $n + c$ 合并
• 最后统计连通分量个数 $k$
• 答案就是 $k - 1$

代码解释

#include <bits/stdc++.h>
#define N 400010
using namespace std;

int a[N], n, m, q, x, y, i, ans;

int Find(int x) {
    return a[x] == x ? x : (a[x] = Find(a[x]));
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    
    // 初始化并查集，前n个是行，后m个是列
    for (i = 1; i <= n + m; i++)
        a[i] = i;
    
    // 处理每个已有的元素
    for (i = 1; i <= q; i++) {
        scanf("%d%d", &x, &y);
        x = Find(x);           // 找到行节点所在集合
        y = Find(y + n);       // 找到列节点所在集合（偏移n）
        a[x] = y;              // 合并集合
    }
    
    // 统计连通分量个数
    for (i = 1; i <= n + m; i++)
        if (a[i] == i)
            ans++;
    
    // 输出需要购买的样品数
    printf("%d\n", ans - 1);
    return 0;
}

复杂度分析

• 时间复杂度：$O((n+m+q) \cdot \alpha(n+m))$，其中 $\alpha$ 是反阿克曼函数，实际运行效率接近线性
• 空间复杂度：$O(n+m)$

算法标签

• 并查集
• 二分图
• 连通分量
• 图论建模

样例验证

样例1：2×2表格，已有3个元素

• 初始连通分量：1个
• 需要购买：1-1=0个

样例2：1×5表格，已有3个元素

• 初始连通分量：3个（因为只有1行，无法连接不同列）
• 需要购买：3-1=2个

样例3：4×3表格，已有6个元素

• 初始连通分量：2个
• 需要购买：2-1=1个

这种解法巧妙地利用了图论模型，将化学反应规则转化为图的连通性问题，从而用简单的并查集算法高效解决了问题。