मान लीजिए हमारे पास एक ऐरे है जो चरों के बीच संबंधों को दर्शाने वाले समीकरणों का प्रतिनिधित्व करता है। प्रत्येक स्ट्रिंग equations[i] की लंबाई 4 होती है और दो रूपों में से एक लेती है: "a==b" या "a!=b"। यहां a और b लोअरकेस अक्षर हैं जो एक-अक्षर वाले चर नामों का प्रतिनिधित्व करते हैं। हमें true खोजना है यदि और केवल यदि चर नामों को पूर्णांक निर्दिष्ट करना संभव है ताकि सभी दिए गए समीकरण संतुष्ट हों।
यदि इनपुट है: ["a==b","b==c","a==c"], तो उत्तर true होगा।
समाधान दृष्टिकोण
getParent() विधि परिभाषित करें जो यूनियन-फाइंड में पैरेंट खोजती है
दो ऐरे equal और notEqual बनाएं, एक पैरेंट मैप बनाएं
सभी समीकरणों को पार्स करके समानता और असमानता में अलग करें
समानता समीकरणों के लिए यूनियन ऑपरेशन करें
असमानता समीकरणों की जांच करें - यदि एक ही सेट में हैं तो false लौटाएं
अंत में true लौटाएं
C++ कार्यान्वयन
#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;
}
};
int main(){
vector<string> v1 = {"a==b","b==c","a==c"};
Solution ob;
cout << (ob.equationsPossible(v1));
return 0;
}
इनपुट
["a==b","b==c","a==c"]
आउटपुट
true