1
class Solution:
2
    def equationsPossible(self, equations: List[str]) -> bool:
3
        from collections import defaultdict
4

5
        g = defaultdict(list)
6
        for e in equations:
7
            if e[1] == "=":
8
                x = e[0]
9
                y = e[3]
10
                g[x].append(y)
11
                g[y].append(x)
12

13
        # marked the connected components as 0,1,2,...,25
14
        ccs = defaultdict(lambda: -1)  # -1 means unmarked or unseen
15

16
        def dfs(node, cc):
17
            if node not in ccs:
18
                ccs[node] = cc
19
                for neighbour in g[node]:
20
                    dfs(neighbour, cc)
21

22
        for i in range(26):
23
            dfs(chr(i + 97), i)
24

25
        for e in equations:
26
            if e[1] == "!":
27
                x = e[0]
28
                y = e[3]
29
                if ccs[x] == ccs[y]:
30
                    return False
31
        return True