721_Accounts_Merge.java

classSolution {
publicList<List<String>> accountsMerge(List<List<String>> accounts) {
UnionFinduf = newUnionFind(accounts.size());

Map<String, Integer> emailToAcc = newHashMap<>();

for (inti = 0; i < accounts.size(); i++) {
for (intj = 1; j < accounts.get(i).size(); j++) {
Stringemail = accounts.get(i).get(j);

if (emailToAcc.containsKey(email)) {
intprevParent = emailToAcc.get(email);
uf.union(prevParent, i);
 } else {
emailToAcc.put(email, i);
 }
 }
 }

Map<Integer, Set<String>> emailsForAcc = newHashMap<>();

for (inti = 0; i < accounts.size(); i++) {
intparent = uf.find(i);
List<String> emails = accounts.get(i);

emailsForAcc.putIfAbsent(parent, newHashSet<>());
emailsForAcc.get(parent).addAll(emails.subList(1, emails.size()));
 }

List<List<String>> result = newArrayList<>();

for (intkey : emailsForAcc.keySet()) {
List<String> temp = newArrayList<>();
temp.addAll(emailsForAcc.get(key));
Collections.sort(temp);
temp.add(0, accounts.get(key).get(0));
result.add(temp);
 }

returnresult;
 }

privateclassUnionFind {
privateint[] parents;

publicUnionFind(intn) {
parents = newint[n];

for (inti = 0; i < parents.length; i++) {
parents[i] = i;
 }
 }

publicintfind(intnode) {
if (parents[node] == node) {
returnnode;
 }
parents[node] = find(parents[parents[node]]);
returnparents[node];
 }

publicvoidunion(inti, intj) {
intp1 = find(i), p2 = find(j);
if (p1 == p2) {
return;
 }
parents[p2] = p1;
 }
 }
}