Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.
Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.
Example 1:
Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second. There is no way to assign the variables to satisfy both equations.
Example 2:
Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
Example 3:
Input: ["a==b","b==c","a==c"]
Output: true
Example 4:
Input: ["a==b","b!=c","c==a"]
Output: false
Example 5:
Input: ["c==c","b==d","x!=z"]
Output: true
Note:
1 <= equations.length <= 500equations[i].length == 4-
equations[i][0]andequations[i][3]are lowercase letters -
equations[i][1]is either'='or'!' -
equations[i][2]is'='
class Solution {
private:
int f[];
void init(){
for (int i=;i<;i++)
f[i] = i;
}
int get_f(int x) {
if (int(f[x]) == int(x)) {
return x;
}
return f[x] = get_f(f[x]); // wrong
}
void merge(int a, int b){
a = get_f(a); // wrong
b = get_f(b);
f[a] = b;
}
bool is_same_set(int a, int b){
if (get_f(a) == get_f(b))
return true;
return false;
}
public:
bool equationsPossible(vector<string>& equations) {
init();
for (string s : equations){ // first: ==
cout<<s<<endl;
int a = s[] - 'a'; // wrong
int b = s[] - 'a';
if (s[] == '=')
merge(a, b);
}
for (string s : equations){ // second: !=
cout<<s<<endl;
int a = s[] - 'a'; // wrong
int b = s[] - 'a';
if (s[] == '!')
if (is_same_set(a, b))
return false;
}
return true;
}
};