ความพึงพอใจของสมการความเท่าเทียมกันใน C++

สมมติว่าเรามีอาร์เรย์ถ้าสมการที่แสดงความสัมพันธ์ระหว่างตัวแปร ตอนนี้สมการสตริงแต่ละรายการ[i] มีความยาว 4 และใช้รูปแบบที่แตกต่างกันสองรูปแบบ:"a==b" หรือ "a!=b" ในที่นี้ a และ b เป็นอักษรตัวพิมพ์เล็กซึ่งใช้แทนชื่อตัวแปรที่มีตัวอักษรตัวเดียว ดังนั้นเราต้องค้นหาว่าจริงหรือไม่ก็ต่อเมื่อสามารถกำหนดจำนวนเต็มให้กับชื่อตัวแปรเพื่อให้เป็นไปตามสมการที่กำหนดทั้งหมดได้

หากอินพุตมีลักษณะดังนี้:["a==b","b==c","a==c"] คำตอบจะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า getParent() ซึ่งจะใช้อักขระ x และแผนที่ m ซึ่งจะทำงานดังนี้ −

• ถ้า m[x] =x ให้คืนค่า x

• มิฉะนั้นให้ตั้งค่า m[x] :=getParent(m[x], m) และคืนค่า m[x]

• จากวิธีหลัก ให้ทำดังนี้ −

• กำหนดสองอาร์เรย์ที่เท่ากันและ notEqual สร้างแผนที่ที่เรียกว่าพาเรนต์

• n :=ขนาดของ e

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • set parent[e[i, 0]] :=e[i, 0], parent[e[i, 3]] :=e[i, 3]

  • ถ้า e[i, 1] เป็นเครื่องหมายเท่ากับ ให้แทรก i ลงในอาร์เรย์ที่เท่ากัน มิฉะนั้น ให้ใส่ i ลงในอาร์เรย์ notEqual

• สำหรับฉันในช่วง 0 ถึงขนาดเท่ากับ – 1

  • ดัชนี :=เท่ากับ[i], ตั้งค่า u, v เป็น e[ดัชนี, 0] และ e[ดัชนี, 3]

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

    ผู้ปกครอง

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดไม่เท่ากัน – 1

  • ดัชนี :=notEqual[i], ตั้งค่า u, v เป็น e[index, 0] และ e[index, 3]

  • ถ้า getParent(u, parent) =getParent(v, parent) ให้คืนค่าเท็จ

• คืนความจริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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