LeetCode Solutions

			

class UnionFind {
 public:
  UnionFind(int n) : sz(n, 1), id(n) {
    iota(begin(id), end(id), 0);
  }

  void unionBySize(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (sz[i] < sz[j]) {
      sz[j] += sz[i];
      id[i] = j;
    } else {
      sz[i] += sz[j];
      id[j] = i;
    }
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector<int> sz;
  vector<int> id;
};

class Solution {
 public:
  vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    vector<vector<string>> ans;
    unordered_map<string, int> emailToIndex;        // {email: index}
    unordered_map<int, set<string>> indexToEmails;  // {index: {emails}}
    UnionFind uf(accounts.size());

    for (int i = 0; i < accounts.size(); ++i) {
      const string name = accounts[i][0];
      for (int j = 1; j < accounts[i].size(); ++j) {
        const string email = accounts[i][j];
        const auto it = emailToIndex.find(email);
        if (it == emailToIndex.end()) {
          // Only record if it's the first time we see thie email
          emailToIndex[email] = i;
        } else {
          // Otherwise, union i w/ emailToIndex[index]
          uf.unionBySize(i, it->second);
        }
      }
    }

    for (const auto& [email, index] : emailToIndex)
      indexToEmails[uf.find(index)].insert(email);

    for (const auto& [index, emails] : indexToEmails) {
      const string name = accounts[index][0];
      vector<string> row{name};
      row.insert(end(row), begin(emails), end(emails));
      ans.push_back(row);
    }

    return ans;
  }
};

			

class UnionFind {
  public UnionFind(List<List<String>> accounts) {
    for (List<String> account : accounts)
      for (int i = 1; i < account.size(); ++i) {
        final String email = account.get(i);
        id.putIfAbsent(email, email);
      }
  }

  public void union(final String u, final String v) {
    id.put(find(u), find(v));
  }

  public String find(final String u) {
    if (u != id.get(u))
      id.put(u, find(id.get(u)));
    return id.get(u);
  }

  private Map<String, String> id = new HashMap<>();
}

class Solution {
  public List<List<String>> accountsMerge(List<List<String>> accounts) {
    List<List<String>> ans = new ArrayList<>();
    Map<String, String> emailToName = new HashMap<>();
    Map<String, TreeSet<String>> idEmailToEmails = new HashMap<>();
    UnionFind uf = new UnionFind(accounts);

    // Get {email: name} mapping
    for (final List<String> account : accounts)
      for (int i = 1; i < account.size(); ++i)
        emailToName.putIfAbsent(account.get(i), account.get(0));

    // Union emails
    for (final List<String> account : accounts)
      for (int i = 2; i < account.size(); ++i)
        uf.union(account.get(i), account.get(i - 1));

    for (final List<String> account : accounts)
      for (int i = 1; i < account.size(); ++i) {
        final String id = uf.find(account.get(i));
        idEmailToEmails.putIfAbsent(id, new TreeSet<>());
        idEmailToEmails.get(id).add(account.get(i));
      }

    for (final String idEmail : idEmailToEmails.keySet()) {
      List<String> emails = new ArrayList<>(idEmailToEmails.get(idEmail));
      final String name = emailToName.get(idEmail);
      emails.add(0, name);
      ans.add(emails);
    }

    return ans;
  }
}