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