मान लीजिए कि हमारे पास एक सरणी है यदि समीकरण जो चर के बीच संबंधों का प्रतिनिधित्व करते हैं, अब प्रत्येक स्ट्रिंग समीकरण [i] की लंबाई 4 है और दो अलग-अलग रूपों में से एक लेता है:"ए ==बी" या "ए! =बी"। यहां, ए और बी लोअरकेस अक्षर हैं, जो एक-अक्षर चर नामों का प्रतिनिधित्व कर रहे हैं। इसलिए हमें सत्य खोजना होगा यदि और केवल यदि चर नामों के लिए पूर्णांक निर्दिष्ट करना संभव है ताकि सभी दिए गए समीकरणों को संतुष्ट किया जा सके।
यदि इनपुट इस प्रकार है:["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, 0]]:=ई [i, 0], माता-पिता [ई [i, 3]]:=ई [i, 3]
-
यदि e[i, 1] बराबर चिह्न है, तो i को समान सरणी में डालें, अन्यथा i को समान सरणी में डालें
-
-
मैं के लिए 0 से बराबर के आकार में - 1
-
अनुक्रमणिका :=बराबर[i], u, v को e[index, 0] और e[index, 3]
के रूप में सेट करें -
माता-पिता [getParent (यू, माता-पिता)]:=माता-पिता [getParent (v, माता-पिता)]
-
-
मेरे लिए 0 से लेकर not समान के आकार तक - 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