题目描述

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: “a==b” or “a!=b”.  Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

样例

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

算法1

并查集

第一步 只看’==’ 把所有相等的放入一个连通块
第二部 只看’!=’ 检查是不是不等的在同一个连通块 不等号前后两个字母在同一个连通块返回 false
走完没有矛盾返回true

用了路径压缩会快一点

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    vector<int> father;
    int find(int x) {
        int a =x;
        while(father[a]!=a) a= father[a];
        // 路径压缩
        int b =x;
        while(b != a){
            father[b] =a;
            b = father[b];
        }

        return a;
    }

    void uni(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        else father[fy] = fx;
    }

    bool equationsPossible(vector<string>& equations) {
        father = vector<int>(26);
        for (int i = 0; i < 26; i++) {
            father[i] = i;
        }

        for (auto &s : equations) {
            if (s[1] == '=')  uni(s[0] - 'a', s[3] - 'a');
        }

        for (auto &s : equations) {
            if (s[1] == '!') {
                int fx = find(s[0] - 'a'), fy = find(s[3] - 'a');
                if (fx == fy) return false;
            }
        }

        return true;
    }
};