哈喽各位，我是前端小L。
欢迎来到我们的图论专题第二十二篇！并查集（Union-Find）最擅长维护的是什么？是**“集合”。而在逻辑学中，“相等”关系（Equality）天然就具有传递性**（若 a==b 且 b==c，则 a==c），这正好对应了并查集中的连通性。
今天，我们要面对一组混杂着 == 和 != 的方程组。
-
== 代表“连接”（Union）。
-
!= 代表“冲突检查”（Check）。
我们的策略非常清晰：先把所有宣称是“朋友”的人聚在一起，然后再检查那些宣称是“敌人”的人，有没有混在同一个圈子里。
力扣 990. 等式方程的可满足性
https://leetcode.cn/problems/satisfiability-of-equality-equations/
题目分析：
-
输入：一个字符串数组 equations。每个字符串形如 "a==b" 或 "a!=b"。变量名只有小写字母 'a' 到 'z'。
-
目标：判断这组方程是否逻辑自洽。如果存在矛盾（例如 a==b, b==c 但 a!=c），返回 false；否则返回 true。
核心洞察：处理顺序是关键 如果我们一边处理 == 一边处理 !=，可能会出问题。 比如：a!=b, b==c, a==c。
看 a!=b：目前 a 和 b 不连通，没毛病。
看 b==c：连通 b 和 c。
看 a==c：连通 a 和 c。 这就漏掉了矛盾！因为 a 和 c 连通后，通过 c 这个中介，a 和 b 其实也连通了，这就违背了第一条 a!=b。
正确的策略：
先礼：无视所有 !=，先把所有 == 的关系处理完，构建好所有的“等价集合”（连通分量）。
后兵：遍历所有 != 的关系，检查每一对变量。如果它们在并查集中竟然拥有同一个老大（即它们是等价的），那就自相矛盾了！
算法流程：两遍扫描
初始化并查集：
-
由于变量只是 'a'-'z'，我们只需要一个大小为 26 的 parent 数组。parent[i] = i。
第一遍扫描 (==)：
-
遍历所有方程。如果中间符号是 ==（eq[1] == '='）：
-
提取变量 u = eq[0] – 'a', v = eq[3] – 'a'。
-
执行 union(u, v)。
-
第二遍扫描 (!=)：
-
再次遍历所有方程。如果中间符号是 !=（eq[1] == '!'）：
-
提取变量 u, v。
-
审判时刻：检查 find(u) 是否等于 find(v)。
-
如果相等，说明 u 和 v 在之前的等式逻辑中已经被判定为“相等”了，现在你又说它俩不等，这就是逻辑矛盾！直接返回 false。
-
通过：如果所有 != 检查都平安无事，返回 true。
代码实现 (轻量级并查集)
因为只需要处理26个字母，我们可以直接把并查集的逻辑写在主函数里，或者写一个极简的内部类。
C++
#include <vector>
#include <string>
#include <numeric>
using namespace std;
class Solution {
private:
// 简单的并查集实现
vector<int> parent;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
public:
bool equationsPossible(vector<string>& equations) {
// 1. 初始化并查集，容量 26
parent.resize(26);
iota(parent.begin(), parent.end(), 0); // 0, 1, …, 25
// 2. 第一遍扫描：处理所有 "=="
for (const string& eq : equations) {
if (eq[1] == '=') {
int u = eq[0] – 'a';
int v = eq[3] – 'a';
unite(u, v);
}
}
// 3. 第二遍扫描：检查所有 "!="
for (const string& eq : equations) {
if (eq[1] == '!') {
int u = eq[0] – 'a';
int v = eq[3] – 'a';
// 如果 u 和 v 属于同一个集合（相等），但等式要求不等 -> 矛盾
if (find(u) == find(v)) {
return false;
}
}
}
// 4. 没有矛盾
return true;
}
};
深度复杂度分析
-
N：方程的数量。
-
时间复杂度 O(N)：
-
我们遍历了方程数组两次。
-
每次并查集操作（find/unite）在路径压缩下接近 O(1)（准确说是阿克曼反函数，对于26个节点简直快到飞起）。
-
所以总时间是线性的。
-
-
空间复杂度 O(1)：
-
parent 数组的大小固定为 26，是常数级空间。
-
总结：并查集——处理等价关系的专家
今天这道题，展示了并查集在逻辑推理中的应用。它告诉我们：
凡是涉及“分组”、“归类”、“等价传递”的问题，都可以抽象为并查集的模型。
-
Union = 建立等价关系。
-
Find = 验证等价关系。
通过巧妙的两遍扫描（先建关系，后查冲突），我们轻松破解了这个逻辑谜题。
在下一篇中，我们将挑战一个更加复杂、更贴近实际业务的并查集应用——“账户合并”。当一个用户拥有多个邮箱，而不同的邮箱列表又存在交集时，我们该如何理清这些混乱的账户关系？
下期见！
