等式方程的可满足性
class Solution {
public:
int find(vector<int>& father,int x){
if(father[x]!=x)father[x]= find(father,father[x]);//如果father[x]不是源头，继续往前找
return father[x];
}
void un(vector<int>& father,int x,int y){
father[find(father,x)]=find(father,y);//y的源头等于x的源头
}
bool equationsPossible(vector<string>& equations) {
int res=0;
int n=equations.size(),m=equations[0].size();
vector<int>father(26+1,-1);
for(int i=0;i<=26;++i){
father[i]=i;
}
for(int i=0;i<n;++i){
int ch1=equations[i][0]-'a';
int ch2=equations[i][3]-'a';
string op=equations[i].substr(1,2);
if(op=="==")un(father,ch1,ch2);
}
for(int i=0;i<n;++i){
int ch1=equations[i][0]-'a';
int ch2=equations[i][3]-'a';
char op=equations[i][1];
if(op=='!'){
if(find(father,ch1)==find(father,ch2))return false;
}
}
return true;
}
};