题目

原题链接

等式方程的可满足性

思路

• 定义一个长度为26（变量为小写字母）的数组充当并查集，并将数组中的元素初始化为 -1
• 判断“==”并合并元素，将相等的放在一个集合中
• 判断“!=”；不等的如果在一个集合中，则矛盾返回false；否则，返回true

C++代码

class Solution 
{
public:bool equationsPossible(vector<string>& equations) {// 初始化并查集vector<int> ufs(26, -1);auto findRoot = [&ufs](int x) {int parent = x;while (ufs[parent] >= 0) {parent = ufs[parent];}return parent;};// 判断“==”并合并元素，将相等的放在一个集合中for(auto e : equations){if(e[1] == '='){int parent1 = findRoot(e[0] - 'a');int parent2 = findRoot(e[3] - 'a');if(parent1 != parent2){ufs[parent1] += ufs[parent2];ufs[parent2] = parent1;}}}// 判断“!=”；不等的如果在一个集合中，则矛盾返回false；否则，返回truefor(auto e : equations){if(e[1] == '!'){int parent1 = findRoot(e[0] - 'a');int parent2 = findRoot(e[3] - 'a');if(parent1 == parent2){return false;}}}return true;}
};