等式方程的可满足性 图解题解

这道题到底在问什么

输入

["a==b","b==c","c==d","a!=d"]

输出

false

另一例

["a==b","b!=c"] → true

最优解：一步一步想明白

1. 3关键顺序：先把所有「相等」的变量并进同一组，再回头看每条「不等」。如果某条 a!=b 里的 a、b 居然已经在同一组里，就矛盾了。
2. 4每个字母记一个「老大(根)」parent[i]。find=顺着 parent 一路找到根；union(a,b)=把 a 的根挂到 b 的根下。相等就 union，最后同根 = 必相等。盯住下面节点的连线和颜色怎么变。
3. 5parent=[a,b,c,d,e]，每人一组开局每个字母自成一组，parent[i]=i，自己是自己的老大（颜色各不同）。e 这次没出现在任何方程里，但也在表里、独自一组。
4. 6find(a)=a, find(b)=b 不同 → 可并第一遍只处理「==」。第 1 条 a==b：先各自 find 根。find(a)=a、find(b)=b，根不同，说明还没并到一起，可以 union（两个圈被点亮）。
5. 7parent[a]=b，{a,b} 一组把 a 的根挂到 b 的根下：parent[a]=b。a 长出一条箭头指向 b，两人同色成一组，组数从 5 减到 4。union 挂的是根，不是节点本身。
6. 8find(b)=b, find(c)=c 不同 → 可并第 2 条 b==c：find(b)=b、find(c)=c，根不同，可以并。注意 a 已经挂在 b 下面了，接下来并 b 会把 a 一起带走。
7. 9parent[b]=c，{a,b,c} 一组把 b 的根挂到 c 的根下：parent[b]=c。现在 a→b→c 连成一串，根都是 c，{a,b,c} 同色一组。a 没被直接动过，却因为传递也并了进来——这就是相等的连锁。
8. 10find(c)=c, find(d)=d 不同 → 可并第 3 条 c==d：find(c)=c、find(d)=d，根不同，可以并。这一并，会把整串 a-b-c 都接到 d 上。
9. 11parent[c]=d，{a,b,c,d} 一大组parent[c]=d。a→b→c→d 全连成一条链，根都是 d，{a,b,c,d} 合成一大组，组数降到 2（只剩这一大组和孤零零的 e）。
10. 12{a,b,c,d} 同根=d，{e} 独立所有「==」处理完：a、b、c、d 全归到根 d，是同一组（必须彼此相等）；e 没人和它相等，独自一组。下面进第二遍，回头逐条查「!=」。
11. 13从 a 出发顺 parent 找根第二遍只查「!=」，本例唯一一条是 a!=d。先算 find(a)：从 a 出发（点亮 a），顺着箭头一格格往上爬找根。
12. 14沿链向上：a→b→ca 的 parent 是 b，b 的 parent 是 c——一路点亮 a、b、c 往上爬。还没到根（c 的 parent 还是 d），继续。
13. 15两根都是 d → 同根！爬到顶，find(a)=d；而 find(d)=d。两边的根都是 d，相同！可前三条等式已逼着 a 和 d 必须相等，这里 a!=d 却要它俩不等——直接矛盾。
14. 16parent[a] 直接改指向 cfind 爬链时顺手做路径压缩：把 a 的箭头直接改指向更上层的 c（parent[a]=c）。下次再 find(a) 就少爬一格。注意根没变、分组没变，只是链被「踩短」了，find 越用越快。
15. 17存在 != 却同根 → 无解只要有任意一条「!=」的两边落在同一组（整组点亮报警），整组方程就无法同时成立，立刻返回 false。本例答案就是 false。
16. 18赋的「具体值」无所谓，重要的是分组：相等的必须同组（同值），不等的必须不同组。只要分组本身不打架，就一定能找到合法赋值。无穷的赋值问题，就这样变成了有限的分组问题。
17. 19并查集清空，准备并 a==b换个不矛盾的用例 ["a==b","a==e","b!=c"]，并查集从头重置（parent[i]=i，5 组）。第一遍先点亮 a、b，准备处理 a==b。
18. 20parent[a]=b，{a,b} 一组处理 a==b：parent[a]=b，a、b 同色一组，组数 5→4。c 仍然独立，没人和它相等。
19. 21挂根 parent[b]=e，{a,b,e} 一组再加一条 a==e：a 的根是 b，e 的根是 e，挂根 parent[b]=e。a→b→e 串起来，{a,b,e} 同组，组数 4→3。挂的依旧是根 b，不是 a 本身。
20. 22b 的根 = e（沿 b→e）查 b!=c 前先各自找根。find(b)：从 b 顺箭头爬到 e（点亮 b、e），所以 b 的根是 e。
21. 23find(b)=e, find(c)=c 不同 → 不冲突再看 find(c)=c。find(b)=e、find(c)=c，两个根不同，b 和 c 本就不在一组，这条不等式没被违反。
22. 24无任何 != 同组 → true所有不等式都查完，没有一条的两边落在同一组里 → 返回 true。和前面那个 false 的用例对比，差别就在那条 != 的两边到底同不同根。
23. 25如果一边并 == 一边查 !=，可能后面还有等式没并进来，导致漏判。所以铁律是两遍：第一遍只 union 等式，第二遍才检查不等式。
24. 29只并了 a==b 就抢查 a!=d → 误判 true回到第一个用例：假如只并了 a==b 就急着查 a!=d，此时 find(a)=b、find(d)=d 根不同，误以为没冲突。可后面 b==c、c==d 一并，a 和 d 就同组了——所以必须先并完所有等式才能查不等。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def equationsPossible(self, equations):
        parent = list(range(26))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # 路径压缩
                x = parent[x]
            return x
        for eq in equations:        # 第一遍: 只并 ==
            if eq[1] == '=':
                a, b = ord(eq[0]) - 97, ord(eq[3]) - 97
                parent[find(a)] = find(b)
        for eq in equations:        # 第二遍: 查 !=
            if eq[1] == '!':
                a, b = ord(eq[0]) - 97, ord(eq[3]) - 97
                if find(a) == find(b):
                    return False
        return True

class Solution {
public:
    vector<int> parent;
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool equationsPossible(vector<string>& equations) {
        parent.resize(26);
        for (int i = 0; i < 26; ++i) parent[i] = i;
        for (const string& eq : equations)
            if (eq[1] == '=')
                parent[find(eq[0] - 'a')] = find(eq[3] - 'a');
        for (const string& eq : equations)
            if (eq[1] == '!')
                if (find(eq[0] - 'a') == find(eq[3] - 'a'))
                    return false;
        return true;
    }
};

class Solution {
    int[] parent;
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    public boolean equationsPossible(String[] equations) {
        parent = new int[26];
        for (int i = 0; i < 26; i++) parent[i] = i;
        for (String eq : equations)
            if (eq.charAt(1) == '=')
                parent[find(eq.charAt(0) - 'a')] = find(eq.charAt(3) - 'a');
        for (String eq : equations)
            if (eq.charAt(1) == '!')
                if (find(eq.charAt(0) - 'a') == find(eq.charAt(3) - 'a'))
                    return false;
        return true;
    }
}

复杂度

面试官可能追问