※ 引述《pandix (面包屌)》之铭言：
: 990. Satisfiability of Equality Equations
这题我今天上班的时候有解
看到的时候没想到可以用并查集来解
而且我并查集忘光光了还复习了一下实现方法
一开始是想用无向图
我参考你的概念然后做一点点改良：
1.不排序整个阵列，遍历两次阵列，第一次遍历 == 的 第二次遍历 != 的
2.时间复杂度比排序好一些，排序复杂度 O(nlogn) 遍历两次复杂度 O(2n)
Java Code：
class Solution {
public boolean equationsPossible(String[] equations) {
int[] root = new int[26];
for(int i = 0; i < 26; i++) root[i] = i;
for(String eq : equations) {
if(eq.charAt(1) == '!') continue;;
int a = eq.charAt(0), b = eq.charAt(3);
root[find(root, a - 'a')] = find(root, b - 'a');
}
for(String eq : equations) {
if(eq.charAt(1) == '=') continue;;
int a = eq.charAt(0), b = eq.charAt(3);
if(root[find(root, a - 'a')] == find(root, b - 'a'))
return false;
}
return true;
}
private int find(int[] root, int x) {
return root[x] == x ? x : find(root, root[x]);
}
}