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]

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• দুটি অ্যারে সমান এবং সমান নয়, অভিভাবক নামে একটি মানচিত্র তৈরি করুন

• n :=e

  এর আকার

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • অভিভাবক সেট করুন [e[i, 0]] :=e[i, 0], অভিভাবক[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)] :=parent[getParent(v, parent)]

• i এর জন্য 0 থেকে notEqual - 1

  এর আকার

  • index :=notEqual[i], e[index, 0] এবং e[index, 3] হিসাবে u, v সেট করুন

  • যদি 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