C++での等式方程式の充足可能性

変数間の関係を表す方程式の配列があるとします。ここで、各文字列方程式[i]の長さは4で、「a ==b」または「a！=b」の2つの異なる形式のいずれかを取ります。ここで、aとbは小文字で、1文字の変数名を表します。したがって、与えられたすべての方程式を満たすように変数名に整数を割り当てることができる場合にのみ、真を見つける必要があります。

入力が["a==b"、 "b ==c"、 "a ==c"]の場合、答えは真になります。

これを解決するには、次の手順に従います-

• getParent（）というメソッドを定義します。これは、文字xとマップmを取り、次のように機能します-

• m [x] =xの場合、xを返します

• それ以外の場合は、m [x]：=getParent（m [x]、m）を設定し、m [x]

  を返します。

• メインの方法から、次のようにします-

• 2つの配列が等しいと等しくないことを定義し、親と呼ばれるマップを作成します

• n：=eのサイズ

• 0からn–1の範囲のiの場合

  • set parent [e [i、0]]：=e [i、0]、parent [e [i、3]]：=e [i、3]

  • e [i、1]が等号の場合は、iを等号に挿入します。それ以外の場合は、iをnotEqual配列に挿入します

• 0から等しいサイズのiの場合– 1

  • index：=equal [i]、u、vをe [index、0]およびe [index、3]

    として設定します

  • parent [getParent（u、parent）]：=parent [getParent（v、parent）]

• 0からnotEqual– 1

  のサイズの範囲のiの場合

  • index：=notEqual [i]、u、vをe [index、0]およびe [index、3]

    として設定します

  • getParent（u、parent）=getParent（v、parent）の場合、falseを返します

• trueを返す

理解を深めるために、次の実装を見てみましょう-

例

#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