A.java

class Solution {
  private class DisjointSet {
    private int[] root, size;
    
    private DisjointSet(int n) {
      root = new int[n];
      size = new int[n];
      for (int i = 0; i < n; i++) {
        root[i] = i;
        size[i] = 1;
      }
    }
    
    private int root(int x) {
      return x == root[x] ? x : (root[x] = root(root[x]));
    }
    
    private void join(int a, int b) {
      int x = root(a), y = root(b);
      if (x != y) {
        if (size[x] < size[y]) y = x ^ y ^ (x = y);
        root[y] = x;
        size[x] += size[y];
      }
    }
  }
  
  public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
    Map<String, Integer> map = new HashMap<>();
    int idx = 0;
    for (String[] pair : pairs) {
      for (int i = 0; i < 2; i++) {
        if (!map.containsKey(pair[i])) {
          map.put(pair[i], idx++);
        }
      }
    }
    DisjointSet dsu = new DisjointSet(4005);
    for (String[] pair : pairs) {
      dsu.join(map.get(pair[0]), map.get(pair[1]));
    }
    boolean similar = words1.length == words2.length;
    if (similar) {
      int n = words1.length;
      for (int i = 0; i < n; i++) {
        int x = map.get(words1[i]), y = map.get(words2[i]);
        similar &= dsu.root(x) == dsu.root(y);
      }
    }
    return similar;
  }
  
}