1
class Solution {
2
  static int par[];
3

4
  public static int findPar(int u) {
5
    return par[u] == u ? u : (par[u] = findPar(par[u]));
6
  }
7

8
  public boolean equationsPossible(String[] equations) {
9
    par = new int[26];
10
    for (int i = 0; i < 26; i++) {
11
      par[i] = i;
12
    }
13

14
    /*First perform all the merging operation*/
15
    for (String s : equations) {
16
      int c1 = s.charAt(0) - 'a';
17
      int c2 = s.charAt(3) - 'a';
18
      char sign = s.charAt(1);
19

20
      int p1 = findPar(c1);
21
      int p2 = findPar(c2);
22

23
      if (sign == '=') {
24
        if (p1 != p2) {
25
          if (p1 < p2) {
26
            par[p2] = p1;
27
          } else {
28
            par[p1] = p2;
29
          }
30
        }
31
      }
32
    }
33

34
    /*Now traverse on the whole string and search for any != operation and check if there parents are same*/
35
    for (String s : equations) {
36
      int c1 = s.charAt(0) - 'a';
37
      int c2 = s.charAt(3) - 'a';
38
      char sign = s.charAt(1);
39

40
      int p1 = findPar(c1);
41
      int p2 = findPar(c2);
42

43
      if (sign == '!') {
44
        if (p1 == p2) {
45
          return false;
46
        }
47
      }
48
    }
49
    return true;
50
  }
51
}