# 0721. Accounts Merge
###### tags: `Leetcode` `Medium` `DFS` `Union Find`
Link: https://leetcode.com/problems/accounts-merge/
## 思路
Union Find
DFS
## Code
Union Find O(nlogn) O(n)

class Solution {
    int[] fa;
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Map<String, Integer> emailToIndex = new HashMap<>();
        Map<Integer, String> indexToEmail = new HashMap<>();
        
        //assign number to each email
        for(List<String> acc:accounts){
            for(int i=1; i<acc.size(); i++){
                emailToName.put(acc.get(i), acc.get(0));
                if(!emailToIndex.containsKey(acc.get(i))){
                    int idx = emailToIndex.size();
                    emailToIndex.put(acc.get(i), idx);
                    indexToEmail.put(idx, acc.get(i));
                }
            }
        }
        
        //union find to get all email groups with email index
        fa = new int[emailToIndex.size()];
        for(int i=0; i<fa.length; i++) fa[i] = i;
        for(List<String> acc:accounts){
            int firstEmail = emailToIndex.get(acc.get(1));
            for(int i=2; i<acc.size(); i++){
                combine(firstEmail, emailToIndex.get(acc.get(i)));
            }
        }
        
        //get all email index group
        Map<Integer, List<Integer>> groupedIndex = new HashMap<>();
        for(int i=0; i<fa.length; i++){
            int f = find(i);
            if(!groupedIndex.containsKey(f)) groupedIndex.put(f, new ArrayList<>());
            groupedIndex.get(f).add(i);
        }
        
        //get answer
        List<List<String>> ans = new ArrayList<>();
        for(int f:groupedIndex.keySet()){
            //find the person name of this email index group
            String name = emailToName.get(indexToEmail.get(f));
            //find all the emails he has
            List<String> emails = new ArrayList<>();
            for(int idx:groupedIndex.get(f)){
                emails.add(indexToEmail.get(idx));
            }
            Collections.sort(emails);
            emails.add(0, name);
            ans.add(emails);
        }
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[b]=a;
    }
}