※ 引述《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]);
}
}