class Solution {
    int parent[] = new int[10001]; //maximum constraints
    
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        /* Q34 graph playlist , DSU concept*/ 

        //initializing parent array
        for(int i = 0 ;i < 10001 ; i++)
        parent[i] = i;

        //making a HM< email , uid> so that we can group them 
        HashMap<String , Integer> euid = new HashMap<>();

        //HM to get email -> name 
        HashMap<String ,String > etn = new HashMap<>();

        int uid = 0;

        //grouping emails and updating hashmaps
        for(List<String> account : accounts){
            String name = " ";

            for(String email : account){

                //store name if 1st time
                if(name == " "){
                    name = email;
                    continue;
                }

                //update HM
                if(euid.containsKey(email) == false){
                    euid.put(email , uid);
                    uid++;
                }
                
                if(etn.containsKey(email) == false){
                    etn.put(email , name);
                }

                //finding parents based on euid and merging with 1st email of that group
                int uid_p1 = euid.get(account.get(1));
                int uid_p2 = euid.get(email);

                int p1 = findparent(uid_p1);
                int p2 = findparent(uid_p2);

                if(p1 != p2)
                parent[p2] = p1;
            }
        }

        //grouping parents and emails in HashMap
        HashMap<Integer , List<String>> pte = new HashMap<>();

        for(String email : etn.keySet()){
            //finding uid of email
            int unique_id = euid.get(email);

            //finding parent 
            int par = findparent(unique_id);

            pte.computeIfAbsent(par , k-> new ArrayList<>()).add(email);
        }

        List<List<String>> ans = new ArrayList<>();
        
        //making final answer
        for(List<String> emails : pte.values()){
            
            //finding name against which email will be added
            String name = etn.get(emails.get(0));

            //sorting emails in ascending order
            Collections.sort(emails);

            //adding into answer
            List<String> temp = new ArrayList<>();

            //adding name first
            temp.add(name);

            //adding emails
            for(String email : emails)
            temp.add(email);

            ans.add(temp);
        }

        return ans;
    }

    public int findparent(int u){
        if(parent[u] == u)
        return parent[u];

        int temp = findparent(parent[u]);
        parent[u] = temp;

        return temp;
    }
}