990, satisfiability of equality equation

====

990, satisfiability of equality equation

====

Union_find

====

1. root單元是“字母” 不是給予eq.size

//eq.size是formula size

字母-“a"的差距

即可化為單元vec<int>

2. vec<string> eq

eq[0], [3]是字母單元

eq[1]是判斷

3. go through eq兩次

第一次先處理等於

如果eq[1]=='=' 則root[ep(0)] = root[eq(0)]

第二次處理不等於

如果eq[1]=='!'

但是先前的等於eq 讓單元root相等, 則flase

====

class Solution {

vector<int> root[26]

public equationPossible(vec<string>& equations) {

  

  for 0<26; root[i] = i

  for string eq:equations

    if eq[1] == '='

      root[ find(root, eq[3] -'a') ] = find(root, eq[0] -'a')

  for string eq:equations

    if eq[1] == '!'

      if find(root, eq[3] -'a') == find(root, eq[0] -'a') 

        return false

  return true

}

find(vec<int>root, int x){

  if root[i] == x

    return x

  return find(root, root[x])

}