721. Accounts Merge

This problem can be solved in three steps:

1. bipartite graph matching: we can take name as the left part and email as the right part of a bipartite graph. Apparently, the left part contains accounts.size() nodes and the given list accounts has denoted the map from name to email. So what we need to do is building the map from email to name;
2. put those names sharing at least one email into a set. In order to merge emails, we first need to put names which share the same emails together. Since the number of names is known, it is simple to do so under the help of union find set.
3. merge emails.

public List<List<String>> accountsMerge(List<List<String>> accounts) { // accounts denotes the map from name to email
    List<List<String>> resultList = new ArrayList<List<String>>();
	
    // 1.build the map from email to name
    Map<String, List<Integer>> emailToAccount = new HashMap<String, List<Integer>>();
    for(int i = 0; i < accounts.size(); i++) { 
        List<String> currentAccount = accounts.get(i);
        for(int j = 1; j < currentAccount.size(); j++) {
            if( emailToAccount.get(currentAccount.get(j)) == null )
                emailToAccount.put(currentAccount.get(j), new ArrayList<Integer>());
            emailToAccount.get(currentAccount.get(j)).add(i);
        }
    }
	
    // 2. put those names sharing at least one email into a set: 
    UnionFind uf = new UnionFind(accounts.size());
    for( Map.Entry<String, List<Integer>> entry: emailToAccount.entrySet() ) {
        List<Integer> accountIndexList = entry.getValue();
        int baseIndex = accountIndexList.get(0);
        for(int i = 1; i < accountIndexList.size(); i++)
            uf.union(baseIndex, accountIndexList.get(i));
    }
    List<Integer> mergeList[] = new List[accounts.size()];
    for(int i = 0; i < accounts.size(); i++) {
        int root = uf.find(i);
        if( mergeList[root] == null)
            mergeList[root] = new ArrayList<Integer>();
        mergeList[root].add(i);
    }
	
    // 3.merge emails
    for(int i = 0; i < accounts.size(); i++) {
        if( mergeList[i] != null ) {
            String name = accounts.get(i).get(0);
            Set<String> currentSet = new HashSet<String>();

            for(int j = 0; j < mergeList[i].size(); j++) {
                List<String> account = accounts.get(mergeList[i].get(j));
                currentSet.addAll(account.subList(1, account.size()));
            }

            List<String> currentAccount = new ArrayList<String>(currentSet);
            Collections.sort(currentAccount); // sort the emails
            currentAccount.add(0, name);
            resultList.add(currentAccount);    
        }
    }
    return resultList;
}

class UnionFind{
    int parent[];
    int height[];

    public int find(int i) {
        return parent[i] != i ? find(parent[i]) : parent[i];
    }

    public void union(int i, int j) {
        int pi = find(i);
        int pj = find(j);
        if( height[pi] < height[pj] )
            parent[pi] = pj;
        else if( height[pi] > height[pj] )
            parent[pj] = pi;
        else{
            parent[pi] = pj;
            height[pj]++;
        }
    }

    public UnionFind(int size) {
        parent = new int[size];
        height = new int[size];
        for(int i = 0; i < size; i++) {
            parent[i] = i;
            height[i] = i;
        }
    }
}