C ++中的等式的可满足性
假设我们有一个数组，如果方程表示变量之间的关系，那么现在每个字符串方程[i]的长度为4，并采用两种不同形式之一：“a==b”或“a！=b”。在此，a和b是小写字母，代表一个字母的变量名。因此，当且仅当可以为变量名称分配整数以满足所有给定的方程式时，我们才必须找到true。
如果输入像：[“a==b”，“b==c”，“a==c”]，那么答案将是正确的。
为了解决这个问题，我们将遵循以下步骤-
定义一个名为的方法getParent()，它将使用字符x和映射m，这将如下工作：
如果m[x]=x，则返回x，
否则设置m[x]：=getParent（m[x]，m）并返回m[x]
从主要方法中，执行以下操作-
定义两个数组equal和notEqual，创建一个称为parent的映射
n：=e的大小
对于i，范围为0至n–1
设置parent[e[i，0]]：=e[i，0]，parent[e[i，3]]：=e[i，3]
如果e[i，1]是等号，则将i插入等号数组，否则将i插入notEqual数组
对于范围在0到相等–1的i
index：=equal[i]，将u，v设置为e[index，0]和e[index，3]
父母[getParent(u,parent)]：=父母[getParent（v，父母）]
对于范围从0到不等于1的i
index：=notEqual[i]，将u，v设置为e[index，0]和e[index，3]
如果getParent(u,parent)=getParent(v,parent)，则返回false
返回真
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
char getParent(char x, map <char, char> m){
if(m[x] == x) return x;
return m[x] = getParent(m[x], m);
}
bool equationsPossible(vector<string>& e) {
vector <int> equal;
vector <int> notEqual;
map <char, char> parent;
int n = e.size();
for(int i = 0; i < n; i++){
parent[e[i][0]]= e[i][0];
parent[e[i][3]]= e[i][3];
if(e[i][1] == '='){
equal.push_back(i);
}else{
notEqual.push_back(i);
}
}
for(int i = 0; i < equal.size(); i++){
int idx = equal[i];
char u = e[idx][0];
char v = e[idx][3];
parent[getParent(u, parent)] = parent[getParent(v, parent)];
}
for(int i = 0; i < notEqual.size(); i++){
int idx = notEqual[i];
char u = e[idx][0];
char v = e[idx][3];
if(getParent(u, parent) == getParent(v, parent)) return false;
}
return true;
}
};
main(){
vector<string> v1 = {"a==b","b==c","a==c"};
Solution ob;
cout << (ob.equationsPossible(v1));
}输入值
["a==b","b==c","a==c"]
输出结果
true