LeetCode 990 Satisfiability of Equality Equations

Tag: 图算法 LeetCode Posted on 2022-02-09 14:47:00 Edited on 2022-02-09 15:22:24 Views: 135

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/