Tính thỏa mãn của các phương trình bình đẳng trong C ++

Giả sử chúng ta có một mảng if các phương trình biểu diễn mối quan hệ giữa các biến, bây giờ mỗi phương trình chuỗi [i] có độ dài 4 và có một trong hai dạng khác nhau:"a ==b" hoặc "a! =B". Ở đây, a và b là các chữ cái viết thường, đại diện cho các tên biến gồm một chữ cái. Vì vậy, chúng ta phải tìm đúng nếu và chỉ khi có thể gán các số nguyên cho các tên biến để thỏa mãn tất cả các phương trình đã cho.

Nếu đầu vào là:["a ==b", "b ==c", "a ==c"], thì câu trả lời sẽ là true.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức có tên getParent (), phương thức này sẽ lấy ký tự x và bản đồ m, phương thức này sẽ hoạt động như sau -

• nếu m [x] =x, thì trả về x,

• nếu không thì đặt m [x]:=getParent (m [x], m) và trả về m [x]

• Từ phương thức chính, thực hiện như sau -

• xác định hai mảng bằng nhau và không bằng nhau, tạo một bản đồ có tên là mẹ

• n:=kích thước của e

• cho tôi trong phạm vi từ 0 đến n - 1

  • đặt phụ huynh [e [i, 0]]:=e [i, 0], phụ huynh [e [i, 3]]:=e [i, 3]

  • nếu e [i, 1] là dấu bằng thì chèn i vào mảng bằng, nếu không thì chèn i vào mảng notEqual

• cho tôi trong phạm vi 0 đến kích thước bằng - 1

  • index:=bằng [i], đặt u, v là e [index, 0] và e [index, 3]

  • cha [getParent (u, parent)]:=parent [getParent (v, parent)]

• cho tôi trong phạm vi từ 0 đến kích thước của notEqual - 1

  • index:=notEqual [i], đặt u, v là e [index, 0] và e [index, 3]

  • nếu getParent (u, parent) =getParent (v, parent), thì trả về false

• trả về true

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

["a==b","b==c","a==c"]

Đầu ra

true