import java.util.*;

public class _721 {
    static class Solution1 {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            Map<String, List<Integer>> graph = new HashMap<>();
            for (int i = 0; i < accounts.size(); i++) {
                for (int j = 1; j < accounts.get(i).size(); j++) {
                    graph.computeIfAbsent(accounts.get(i).get(j), k -> new ArrayList<>()).add(i);
                }
            }
            List<Set<Integer>> needToMerge = new ArrayList<>();
            Set<Integer> v = new HashSet<>();
            for (int i = 0; i < accounts.size(); i++) {
                if (v.contains(i)) continue;
                Set<Integer> res = new HashSet<>();
                Set<Integer> cur = new HashSet<>();
                v.add(i);
                cur.add(i);
                while (cur.size() > 0) {
                    res.addAll(cur);
                    Set<Integer> next = new HashSet<>();
                    for (int k : cur) {
                        for (int j = 1; j < accounts.get(k).size(); j++) {
                            for (Integer in : graph.get(accounts.get(k).get(j))) {
                                if (v.contains(in)) continue;
                                next.add(in);
                                v.add(in);
                            }

                        }
                    }
                    cur = next;
                }
                needToMerge.add(res);
            }
            // System.out.println(needToMerge);
            List<List<String>> res = new ArrayList<>();
            for (Set<Integer> set : needToMerge) {
                Set<String> emails = new HashSet<>();
                List<String> cur = new ArrayList<>();
                String name = null;
                for (Integer id : set) {
                    if (name == null) name = accounts.get(id).get(0);
                    for (int j = 1; j < accounts.get(id).size(); j++) {
                        emails.add(accounts.get(id).get(j));
                    }
                }
                // cur.add(name);
                cur.addAll(emails);
                Collections.sort(cur);
                cur.add(0, name);
                res.add(cur);
            }
            return res;
        }
    }

    static class Solution2 {
        public List<List<String>> accountsMerge(List<List<String>> accounts) {
            //其他人Union find 思路,这里自己重新尝试了
            //Union find最核心在于
            // 当 a 连通 b时，b连通 c
            // 那么a 连通 c
            //这里，相同用户最终都会连通相同的 id，通过find来查找连通的的最终id
            Map<String, Integer> emailToIdx = new HashMap<>();
            Map<Integer, TreeSet<String>> unionEmail = new HashMap<>();
            int[] p = new int[accounts.size()];
            for (int i = 0; i < p.length; i++) {
                p[i] = i;
            }
            int idx = 0;
            for (List<String> nameAndEmails : accounts) {
                for (int i = 1; i < nameAndEmails.size(); i++) {
                    String email = nameAndEmails.get(i);
                    //emailToIdx,记录，上个email对应的id,如果，email重复的话，说明相同email对应了不同的id
                    //将当前id与上个id进行连通
                    int parent = emailToIdx.getOrDefault(email, idx);
                    union(p, idx, parent);
                    emailToIdx.put(email, find(p, idx));
                }
                idx++;
            }
            for (int i = 0; i < p.length; i++) {
                int parent = find(p, i);
                // p[i] = parent;
                TreeSet<String> set = unionEmail.computeIfAbsent(parent, key -> new TreeSet<>());
                List<String> account = accounts.get(i);
                for (int j = 1; j < account.size(); j++) {
                    set.add(account.get(j));
                }
            }
            List<List<String>> res = new ArrayList<>();
            for (Integer key : unionEmail.keySet()) {
                List<String> resItem = new LinkedList<>(unionEmail.get(key));
                resItem.add(0, accounts.get(key).get(0));
                res.add(resItem);
            }
            return res;
        }


        private int find(int[] p, int item) {
            return p[item] != item ? find(p, p[item]) : item;
        }

        private void union(int[] p, int a, int b) {
            p[find(p, a)] = find(p, b);
        }
    }
}