990. Satisfiability of Equality Equations
給你很多"xi==yi" / "xi!=yi"，問你有沒有合法的解，有就回傳 True，反之 False
變數名稱都是小寫英文字母。
Example 1:
Input: equations = ["a==b","b!=a"]
Output: false
Example 2:
Input: equations = ["b==a","a==b"]
Output: true
思路:
1.disjoint set經典題，把相等的變數都加到同一個 set 裡就好。
遇到 "!=" 就判斷兩個是不是在同一個 set 裡，是的話就矛盾了
2.避免出現 ["a!=b", "a==b"] 這種先不等式再等式的情況，要先把等式做完
所以先 sort 一次 equations 把等式拿到前面先做
Python code:
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
root = list(range(26))
equations.sort(key = lambda x: x[1] == '!')
def find(x):
if root[x] != x:
root[x] = find(root[x])
return root[x]
for equation in equations:
a, b = ord(equation[0])-97, ord(equation[3])-97,
if equation[1] == '=':
root[find(a)] = find(b)
elif find(a) == find(b):
return False
return True
contest 剛出完一題馬上又幫大家複習一次 disjoint set==