Given an arrayequations of strings that represent relationships between variables, each stringequations[i] has length4and takes one of two different forms:"a==b"or"a!=b". Here,aandbare lowercase letters (not necessarily different) that represent one-letter variable names.
Returntrue if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.
Example
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
静态联通性，使用Union-Find
等号全部连接在一起，再单独判断不等号，如果连接：就false了
Code
class Solution {
class UF {
int[] father;
public UF() {
this.father = new int[26];
for (int i = 0; i < 26; i++) {
father[i] = i;
}
}
int find(int x) {
if (x == father[x]) {
return x;
}
return father[x] = find(father[x]);
}
void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
father[rootA] = rootB;
}
}
}
public boolean equationsPossible(String[] equations) {
UF uf = new UF();
for (String elem : equations) {
int a = elem.charAt(0) - 'a', b = elem.charAt(3) - 'a';
if (elem.charAt(1) == '=') {
uf.union(a, b);
}
}
for (String elem : equations) {
int a = elem.charAt(0) - 'a', b = elem.charAt(3) - 'a';
if (elem.charAt(1) == '!' && uf.find(a) == uf.find(b)) {
return false;
}
}
return true;
}
}
