動機

做兩遍union find!!

Problem

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

 

Example 1:

Input: equations = ["a==b","b!=a"]Output: falseExplanation: 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: equations = ["b==a","a==b"]Output: trueExplanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

Input: equations = ["a==b","b==c","a==c"]Output: true

Example 4:

Input: equations = ["a==b","b!=c","c==a"]Output: false

Example 5:

Input: equations = ["c==c","b==d","x!=z"]Output: true

 

Constraints:

  • 1 <= equations.length <= 500
  • equations[i].length == 4
  • equations[i][0] is a lowercase letter.
  • equations[i][1] is either '=' or '!'.
  • equations[i][2] is '='.
  • equations[i][3] is a lowercase letter.

Sol

用union find把==串起來

但是就算加rank還是會遇到["a==b","e==c","b==c","a!=e"]這種不小心接到小的item的case

class Solution:
    def equationsPossible(self, es: List[str]) -> bool:
        var = set()
        [(var.add(e[0]), var.add(e[3])) for e in es]
        noteq = [(e[0],e[3]) for e in es if e[1] == "!"]
        eq = [(e[0],e[3]) for e in es if e[1] == "="]
        uf = {v:v for v in var}
        rank = defaultdict(int)
        def find(v):
            while v != uf[v]:
                uf[v] = uf[uf[v]]
                v = uf[v]
            return v
        def union(a,b):
            x,y = find(a), find(b)
            if rank[x] >= rank[y]:
                uf[b] = a
                rank[a] += 1
            else:
                uf[a] = b
                rank[b] += 1
        
        [union(a,b) for a,b in eq]
        #print(uf, noteq)
        return all(find(a) != find(b) for a,b in noteq)