等式方程的可满足性

关键顺序：先把所有「相等」的变量并进同一组，再回头看每条「不等」。如果某条 a!=b 里的 a、b 居然已经在同一组里，就矛盾了。

每个字母记一个「老大(根)」parent[i]。find=顺着 parent 一路找到根；union(a,b)=把 a 的根挂到 b 的根下。相等就 union，最后同根 = 必相等。盯住下面节点的连线和颜色怎么变。

初始 · 各自为政：开局每个字母自成一组，parent[i]=i，自己是自己的老大（颜色各不同）。e 这次没出现在任何方程里，但也在表里、独自一组。

第一遍 · 处理 a==b · find 两根：第一遍只处理「==」。第 1 条 a==b：先各自 find 根。find(a)=a、find(b)=b，根不同，说明还没并到一起，可以 union（两个圈被点亮）。

第一遍 · a==b · union 挂根：把 a 的根挂到 b 的根下：parent[a]=b。a 长出一条箭头指向 b，两人同色成一组，组数从 5 减到 4。union 挂的是根，不是节点本身。

第一遍 · 处理 b==c · find 两根：第 2 条 b==c：find(b)=b、find(c)=c，根不同，可以并。注意 a 已经挂在 b 下面了，接下来并 b 会把 a 一起带走。

第一遍 · b==c · union 挂根：把 b 的根挂到 c 的根下：parent[b]=c。现在 a→b→c 连成一串，根都是 c，{a,b,c} 同色一组。a 没被直接动过，却因为传递也并了进来——这就是相等的连锁。

第一遍 · 处理 c==d · find 两根：第 3 条 c==d：find(c)=c、find(d)=d，根不同，可以并。这一并，会把整串 a-b-c 都接到 d 上。

第一遍 · c==d · union 挂根：parent[c]=d。a→b→c→d 全连成一条链，根都是 d，{a,b,c,d} 合成一大组，组数降到 2（只剩这一大组和孤零零的 e）。

第一遍处理完 · 看看分组：所有「==」处理完：a、b、c、d 全归到根 d，是同一组（必须彼此相等）；e 没人和它相等，独自一组。下面进第二遍，回头逐条查「!=」。

第二遍 · 查 a!=d · find(a) 起步：第二遍只查「!=」，本例唯一一条是 a!=d。先算 find(a)：从 a 出发（点亮 a），顺着箭头一格格往上爬找根。

第二遍 · find(a) 爬 a→b→c：a 的 parent 是 b，b 的 parent 是 c——一路点亮 a、b、c 往上爬。还没到根（c 的 parent 还是 d），继续。

第二遍 · find(a)=d & find(d)=d：爬到顶，find(a)=d；而 find(d)=d。两边的根都是 d，相同！可前三条等式已逼着 a 和 d 必须相等，这里 a!=d 却要它俩不等——直接矛盾。

顺手 · 路径压缩(find 的优化)：find 爬链时顺手做路径压缩：把 a 的箭头直接改指向更上层的 c（parent[a]=c）。下次再 find(a) 就少爬一格。注意根没变、分组没变，只是链被「踩短」了，find 越用越快。

判定 · 返回 false：只要有任意一条「!=」的两边落在同一组（整组点亮报警），整组方程就无法同时成立，立刻返回 false。本例答案就是 false。

赋的「具体值」无所谓，重要的是分组：相等的必须同组（同值），不等的必须不同组。只要分组本身不打架，就一定能找到合法赋值。无穷的赋值问题，就这样变成了有限的分组问题。

对照正例 · ["a==b","a==e","b!=c"] · 重置：换个不矛盾的用例 ["a==b","a==e","b!=c"]，并查集从头重置（parent[i]=i，5 组）。第一遍先点亮 a、b，准备处理 a==b。

对照正例 · 第一遍并 a==b：处理 a==b：parent[a]=b，a、b 同色一组，组数 5→4。c 仍然独立，没人和它相等。

对照正例 · 第一遍并 a==e：再加一条 a==e：a 的根是 b，e 的根是 e，挂根 parent[b]=e。a→b→e 串起来，{a,b,e} 同组，组数 4→3。挂的依旧是根 b，不是 a 本身。

对照正例 · 第二遍 find(b) 爬到根 e：查 b!=c 前先各自找根。find(b)：从 b 顺箭头爬到 e（点亮 b、e），所以 b 的根是 e。

对照正例 · 第二遍查 b!=c：再看 find(c)=c。find(b)=e、find(c)=c，两个根不同，b 和 c 本就不在一组，这条不等式没被违反。

对照正例 · 全部查完 · 返回 true：所有不等式都查完，没有一条的两边落在同一组里 → 返回 true。和前面那个 false 的用例对比，差别就在那条 != 的两边到底同不同根。

如果一边并 == 一边查 !=，可能后面还有等式没并进来，导致漏判。所以铁律是两遍：第一遍只 union 等式，第二遍才检查不等式。

易错实演 · 若颠倒顺序会怎样：回到第一个用例：假如只并了 a==b 就急着查 a!=d，此时 find(a)=b、find(d)=d 根不同，误以为没冲突。可后面 b==c、c==d 一并，a 和 d 就同组了——所以必须先并完所有等式才能查不等。

边界三连：特别留意 a!=a：同一个字母自己跟自己永远同根，所以这条永远矛盾，直接 false。

面试常追问「为什么是并查集」「能否泛化」，把「动态合并 + 判同组」这个本质讲清楚就稳了。