মান লেযিয়ে সমীকরণের একটি অ্যারে দেওয়া আছে যা ভেরিয়েবল間ের সম্পর্ক উপস্থাপন করে। প্রতিটি স্ট্রিং equations[i]-র দৈর্ঘ্য ৪ এবং এটি দুটি রূপের যেকোনো একটি নিতে পারে: "a==b" বা "a!=b"। এখানে a এবং b ছোট হাতের অক্ষর, যারা এক-অক্ষরের ভেরিয়েবল নাম উপস্থাপন করে। আমাদের true রিটার্ন করতে হবে যদি এবং কেবল যদি ভেরিয়েবল নামগুলোর জন্য পূর্ণসংখ্যা অ্যাসাইন করা যায় যাতে সব দেওয়া সমীকরণ সन्तুষ্ট হয়। ইনপুট ["a==b","b==c","a==c"] হলে উত্তর true।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
getParent() নামে একটি মেথড সংজ্ঞায়িত করুন, যা character x এবং map m নেবে -
যদি m[x] == x হয়, x রিটার্ন করুন
অন্যথায় m[x] := getParent(m[x], m) সেট করুন এবং m[x] রিটার্ন করুন
মেইন মেথড থেকে -
দুটি অ্যারে equal এবং notEqual, parent নামে একটি ম্যাপ তৈরি করুন
n := e.size()
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
parent[e[i][0]] := e[i][0], parent[e[i][3]] := e[i][3] সেট করুন
যদি e[i][1] == '=' হয়, equal-এ i ইনসার্ট করুন, অন্যথায় notEqual-এ
i = 0 থেকে equal.size()-1 পর্যন্ত লুপ চালান
index := equal[i], u, v := e[index][0], e[index][3]
parent[getParent(u, parent)] := parent[getParent(v, parent)]
i = 0 থেকে notEqual.size()-1 পর্যন্ত লুপ চালান
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
