LeetCode 990 Satisfiability of Equality Equations

    
        标签：
        
            图算法
        
            LeetCode
        
    发布于：2022-02-09 14:47:00
    编辑于：2022-02-09 15:22:24
    浏览量：956

概述

https://leetcode.com/problems/satisfiability-of-equality-equations/

并查集解法

拿到题目，第一想法是，对于所有需要保持值相同的变量，用一个变量去表示这一群变量。

那么一组需要保持一致的变量就算一棵树，每个节点指向其父节点。

处理完所有等式后，我们遍历所有的不等式，要求双方不能在同一颗树内，否则的话就返回 false。

class Solution {
public:
    vector<int> p;
    bool equationsPossible(vector<string>& equations) {
        for (int i = 0; i < 26; i ++) {
            p.push_back(i);
        }
        for (auto e : equations) {
            if (e[1] == '=') {
                unite(e[0], e[3]);
            }
        }
        for (auto e : equations) {
            if (e[1] == '!') {
                if (find(e[0] - 'a') == find(e[3] - 'a')) return false;
            }
        }
        return true;
    }
    
    void unite(char i, char j) {
        int pi = find(i - 'a');
        int pj = find(j - 'a');
        p[pi] = pj;
    }
    
    int find(int i) {
        while (i != p[i]) {
            p[i] = p[p[i]];
            i = p[i];
        }
        return i;
    }
};

Links: leetcode-990-satisfiability-of-equality-equations