LeetCode 721 - Accounts Merge

https://leetcode.com/problems/accounts-merge/description/

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation: 
The first and third John's are the same person as they have the common email "johnsmith@mail.com".
The second John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Note:

The length of accounts will be in the range [1, 1000].

The length of accounts[i] will be in the range [1, 10].

The length of accounts[i][j] will be in the range [1, 30].

X. Union-Find
http://www.cnblogs.com/grandyang/p/7829169.html

这个归组类的问题，最典型的就是岛屿问题(例如Number of Islands II)，很适合使用Union Find来做，LeetCode中有很多道可以使用这个方法来做的题，比如Friend Circles，Graph Valid Tree，Number of Connected Components in an Undirected Graph，和Redundant Connection等等。都是要用一个root数组，每个点开始初始化为不同的值，如果两个点属于相同的组，就将其中一个点的root值赋值为另一个点的位置，这样只要是相同组里的两点，通过find函数得到相同的值。在这里，由于邮件是字符串不是数字，所以root可以用哈希map来代替，我们还需要一个哈希映射owner，建立每个邮箱和其所有者姓名之前的映射，另外用一个哈希映射来建立用户和其所有的邮箱之间的映射，也就是合并后的结果。

首先我们遍历每个账户和其中的所有邮箱，先将每个邮箱的root映射为其自身，然后将owner赋值为用户名。然后开始另一个循环，遍历每一个账号，首先对帐号的第一个邮箱调用find函数，得到其父串p，然后遍历之后的邮箱，对每个遍历到的邮箱先调用find函数，将其父串的root值赋值为p，这样做相当于将相同账号内的所有邮箱都链接起来了。我们下来要做的就是再次遍历每个账户内的所有邮箱，先对该邮箱调用find函数，找到父串，然后将该邮箱加入该父串映射的集合汇总，这样就我们就完成了合并。最后只需要将集合转为字符串数组，加入结果res中，通过owner映射找到父串的用户名，加入字符串数组的首位置

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string>> res;
        unordered_map<string, string> root;
        unordered_map<string, string> owner;
        unordered_map<string, set<string>> m;
        for (auto account : accounts) {
            for (int i = 1; i < account.size(); ++i) {
                root[account[i]] = account[i];
                owner[account[i]] = account[0];
            }
        }
        for (auto account : accounts) {
            string p = find(account[1], root);
            for (int i = 2; i < account.size(); ++i) {
                root[find(account[i], root)] = p;
            }
        }
        for (auto account : accounts) {
            for (int i = 1; i < account.size(); ++i) {
                m[find(account[i], root)].insert(account[i]);
            }
        }
        for (auto a : m) {
            vector<string> v(a.second.begin(), a.second.end());
            v.insert(v.begin(), owner[a.first]);
            res.push_back(v);
        }
        return res;
    }
    string find(string s, unordered_map<string, string>& root) {
        return root[s] == s ? s : find(root[s], root);
    }

https://blog.csdn.net/fuxuemingzhu/article/details/82913712
给出一个账户列表，其中每一个账户由多个字符串组成，第一个字符串为姓名，其余的字符串为在该姓名下注册的邮箱地址。由于同一个人可能有两个不同的账户，判别是否是同一个人所拥有的账户方法就是在不同的账户中发现是否有相同的邮箱地址，如果有相同的邮箱地址，则可判定两个账户为同一人所拥有。现在要做的就是，对给定账户列表中同一个人所拥有的账户进行合并，合并结果为一个人只拥有一个账户，并且该账户包含其所有的邮箱并且不重复。
Note：同一人的账户可能有多个重名邮箱地址，输出的时候要对这部分进行处理去掉冗余部分，并且进行字典序排列。

这个问题本质上是对不同的集合进行处理，因此暴力求解法在这里几乎不可能成功。求解这个问题的方法最经典的思路就是并查集。

那么在本题所涉及的条件下，我们应该满足两个要求。

去除重复元素，并且有序排序

对于这个条件，很容易想到set集合（结合中没有重复元素，而且元素在插入的时候保持字典序），因此在实现的过程中，必要的一步就是将原有的邮箱列表装载到一个set集合中，然后进行如下的操作。

对含有相同元素的集合，进行合并。

这个步骤中，就要我们的刚学的并查集登场了。

首先初始化并查集，使并查集和中的元素（i = 0,1,2…n）与account中的元素(account[0], account1…account[n]）一一对应。
在对应结束后，我们便可以将所有的集合元素遍历一遍，判断哪些集合会有相同的元素。凡是有相同邮箱的账户均合并（此操作在并查集中实现）。
进行完上面的步骤之后，哪些account是属于同一人的，这些关系均会在并查集上体现出来。最后，我们按照并查集的操作，来将元素进行合并即可。

https://blog.csdn.net/likewind1993/article/details/78473302
那么在本题所涉及的条件下，我们应该满足两个要求。

去除重复元素，并且有序排序
对于这个条件，很容易想到set集合（结合中没有重复元素，而且元素在插入的时候保持字典序），因此在实现的过程中，必要的一步就是将原有的邮箱列表装载到一个set集合中，然后进行如下的操作。

对含有相同元素的集合，进行合并。
这个步骤中，就要我们的刚学的并查集登场了。
1. 首先初始化并查集，使并查集和中的元素（i = 0,1,2…n）与account中的元素(account[0], account[1]…account[n]）一一对应。
2. 在对应结束后，我们便可以将所有的集合元素遍历一遍，判断哪些集合会有相同的元素。凡是有相同邮箱的账户均合并（此操作在并查集中实现）。
3. 进行完上面的步骤之后，哪些account是属于同一人的，这些关系均会在并查集上体现出来。最后，我们按照并查集的操作，来将元素进行合并即可。


作者使用全局的数组来进行并查集操作
但是在建立集合的操作中，并没有充分利用条件（如，仅当两个账户名相同时，才有两个账户同属于一个人的可能，即，如果两个账户名不同，则没有继续比较邮箱账号的必要）
其余的算法流程使用并查集的思想就可以很好的理解了：一个账户表示一个元素，初始状态为n个账户，然后对账户的邮箱账号进行遍历，如果有相同的账号，则这两个账户属于同一个集合，接下来申请vector< set < string>> 空间来进行中间赋值管理，将属于同一集合的账户合并。最后整理返回。
Note：vector< set < string> > res; res.resize(n);中使用到了resize(n)函数，相当于new动态申请元素的空间, 即初始化n个元素的变量作用，如果没有这个操作，在接下来直接访问的时候会出错。
const int N = 1000 + 5;
int n, par[N];
int find(int x) {
    return par[x] == x ? x : (par[x] = find(par[x]));
}
void unit(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    par[x] = y;
}
bool same(int x, int y) {
    return find(x) == find(y);
}
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        n = accounts.size();
        for (int i = 0; i < n; i++) par[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) if (!same(i, j)) {
                for (int k = 1; k < accounts[i].size(); k++) for (int t = 1; t < accounts[j].size(); t++) {
                    if (accounts[i][k] == accounts[j][t]) unit(i, j);
                }
            }
        }
        vector<set<string> > res; res.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = find(i);
            for (int j = 1; j < accounts[i].size(); j++) res[par[i]].insert(accounts[i][j]);
        }
        vector<vector<string> > ret;
        for (int i = 0; i < n; i++) if (par[i] == i) {
            vector<string> cur;
            cur.push_back(accounts[i][0]);
            for (auto str : res[i]) cur.push_back(str);
            ret.push_back(cur);
        }
        return ret;
    }

https://leetcode.com/problems/accounts-merge/solution/

As in Approach #1, our problem comes down to finding the connected components of a graph. This is a natural fit for a Disjoint Set Union (DSU) structure.

Algorithm

As in Approach #1, draw edges between emails if they occur in the same account. For easier interoperability between our DSU template, we will map each email to some integer index by using emailToID. Then, dsu.find(email) will tell us a unique id representing what component that email is in.

For more information on DSU, please look at Approach #2 in the article here. For brevity, the solutions showcased below do not use union-by-rank.

• Time Complexity: $O(A \log A)$, where $A = \sum a_i$, and $a_i$ is the length of accounts[i]. If we used union-by-rank, this complexity improves to $O(A \alpha(A)) \approx O(A)$, where $\alpha$ is the Inverse-Ackermannfunction.
• Space Complexity: $O(A)$, the space used by our DSU structure.

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        DSU dsu = new DSU();
        Map<String, String> emailToName = new HashMap();
        Map<String, Integer> emailToID = new HashMap();
        int id = 0;
        for (List<String> account: accounts) {
            String name = "";
            for (String email: account) {
                if (name == "") {
                    name = email;
                    continue;
                }
                emailToName.put(email, name);
                if (!emailToID.containsKey(email)) {
                    emailToID.put(email, id++);
                }
                dsu.union(emailToID.get(account.get(1)), emailToID.get(email));
            }
        }

        Map<Integer, List<String>> ans = new HashMap();
        for (String email: emailToName.keySet()) {
            int index = dsu.find(emailToID.get(email));
            ans.computeIfAbsent(index, x-> new ArrayList()).add(email);
        }
        for (List<String> component: ans.values()) {
            Collections.sort(component);
            component.add(0, emailToName.get(component.get(0)));
        }
        return new ArrayList(ans.values());
    }
}
class DSU {
    int[] parent;
    public DSU() {
        parent = new int[10001];
        for (int i = 0; i <= 10000; ++i)
            parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }

https://leetcode.com/problems/accounts-merge/discuss/109157/JavaC++-Union-Find

1. The key task here is to connect those emails, and this is a perfect use case for union find.
2. to group these emails, each group need to have a representative, or parent.
3. At the beginning, set each email as its own representative.
4. Emails in each account naturally belong to a same group, and should be joined by assigning to the same parent (let's use the parent of first email in that list)

    public List<List<String>> accountsMerge(List<List<String>> acts) {
        Map<String, String> owner = new HashMap<>();
        Map<String, String> parents = new HashMap<>();
        Map<String, TreeSet<String>> unions = new HashMap<>();
        for (List<String> a : acts) {
            for (int i = 1; i < a.size(); i++) {
                parents.put(a.get(i), a.get(i));
                owner.put(a.get(i), a.get(0));
            }
        }
        for (List<String> a : acts) {
            String p = find(a.get(1), parents);
            for (int i = 2; i < a.size(); i++)
                parents.put(find(a.get(i), parents), p);
        }
        for(List<String> a : acts) {
            String p = find(a.get(1), parents);
            if (!unions.containsKey(p)) unions.put(p, new TreeSet<>());
            for (int i = 1; i < a.size(); i++)
                unions.get(p).add(a.get(i));
        }
        List<List<String>> res = new ArrayList<>();
        for (String p : unions.keySet()) {
            List<String> emails = new ArrayList(unions.get(p));
            emails.add(0, owner.get(p));
            res.add(emails);
        }
        return res;
    }
    private String find(String s, Map<String, String> p) {
        return p.get(s) == s ? s : find(p.get(s), p);
    }

public List<List<String>> accountsMerge(List<List<String>> accounts) {

UnionFind uf = new UnionFind(accounts);

for (int i = 1; i < accounts.size(); i++) {

int tmp = i;

Set<Integer> groups = uf.getGroup(getEmails(accounts.get(i))).stream().filter(x -> x < tmp)

.collect(Collectors.toSet());

uf.union(groups, i);

}

Map<Integer, PersonEmail> results = new HashMap<>();

System.out.println(uf);

for (int i = 0; i < accounts.size(); i++) {

results.computeIfAbsent(uf.findRoot(i), tmp -> new PersonEmail()).setName(getName(accounts.get(i)))

.addEmails(getEmails(accounts.get(i)));

}

return results.values().stream().map(pe -> {

List<String> list = new ArrayList<>();

list.add(pe.name);

list.addAll(new TreeSet<>(pe.emails));

return list;

}).collect(Collectors.toList());

}

private static class PersonEmail {

public String name;

public Set<String> emails = new HashSet<>();

public PersonEmail() {

}

public PersonEmail addEmails(Collection<String> emails) {

this.emails.addAll(emails);

return this;

}

public PersonEmail setName(String name) {

this.name = name;

return this;

}

}

private String getName(List<String> account) {

return account == null ? null : account.get(0);

}

private List<String> getEmails(List<String> account) {

return account == null ? new ArrayList<>() : account.subList(1, account.size());

}

private static class UnionFind {

int[] parent;

// TODO make it generic

Map<String, Set<Integer>> emailGroups = new HashMap<>();

int size;

public UnionFind(List<List<String>> accounts) {

parent = new int[accounts.size()];

size = accounts.size();

// Arrays.fill(parent, -1);

for (int i = 0; i < accounts.size(); i++) {

parent[i] = i;

for (String email : accounts.get(i)) {

emailGroups.computeIfAbsent(email, k -> new HashSet<>()).add(i);

}

}

}

public int findRoot(int node) {

if (isRoot(node)) {

return node;

}

int root = findRoot(parent[node]);

parent[node] = root;

return root;

}

public void union(Set<Integer> roots, int newRoot) {

// roots = findNotMergedRoot(roots);

for (int root : roots) {

// parent[root] = newRoot; // WRONG

parent[findRoot(parent[root])] = newRoot;

// size--;

}

}

public Set<Integer> getGroup(List<String> emails) {

Set<Integer> groups = new HashSet<>();

for (String email : emails) {

if (emailGroups.containsKey(email)) {

// emailGroups.put(email, findRootNodes(emailGroups.get(email)));

groups.addAll(emailGroups.get(email));

}

}

return groups;

}

private Set<Integer> findRootNodes(Set<Integer> roots) {

return roots.stream().filter(i -> isRoot(i)).collect(Collectors.toSet());

}

private boolean isRoot(Integer i) {

return parent[i] == i;

}

@Override

public String toString() {

return "UnionFind [parent=" + Arrays.toString(parent) + ", emailGroups=" + emailGroups + ", size=" + size

+ "]";

}

}

Draw an edge between two emails if they occur in the same account. The problem comes down to finding connected components of this graph.

Algorithm

For each account, draw the edge from the first email to all other emails. Additionally, we'll remember a map from emails to names on the side. After finding each connected component using a depth-first search, we'll add that to our answer.

• Time Complexity: $O(\sum a_i \log a_i)$, where $a_i$ is the length of accounts[i]. Without the log factor, this is the complexity to build the graph and search for each component. The log factor is for sorting each component at the end.
• Space Complexity: $O(\sum a_i)$, the space used by our graph and our search.

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap();
        Map<String, ArrayList<String>> graph = new HashMap();
        for (List<String> account: accounts) {
            String name = "";
            for (String email: account) {
                if (name == "") {
                    name = email;
                    continue;
                }
                graph.computeIfAbsent(email, x-> new ArrayList<String>()).add(account.get(1));
                graph.computeIfAbsent(account.get(1), x-> new ArrayList<String>()).add(email);
                emailToName.put(email, name);
            }
        }

        Set<String> seen = new HashSet();
        List<List<String>> ans = new ArrayList();
        for (String email: graph.keySet()) {
            if (!seen.contains(email)) {
                seen.add(email);
                Stack<String> stack = new Stack();
                stack.push(email);
                List<String> component = new ArrayList();
                while (!stack.empty()) {
                    String node = stack.pop();
                    component.add(node);
                    for (String nei: graph.get(node)) {
                        if (!seen.contains(nei)) {
                            seen.add(nei);
                            stack.push(nei);
                        }
                    }
                }
                Collections.sort(component);
                component.add(0, emailToName.get(email));
                ans.add(component);
            }
        }
        return ans;
    }

https://leetcode.com/problems/accounts-merge/discuss/109161/Python-Simple-DFS-with-explanation!!!

X. BFS
http://www.cnblogs.com/grandyang/p/7829169.html

下面这种方法是使用BFS来解的，建立了每个邮箱和其所有出现的账户数组之间的映射，比如还是这个例子：

["John", "a@gmail.com", "b@gmail.com"]

["John", "c@gmail.com", "d@gmail.com"]

["John", "a@gmail.com", "c@gmail.com"]

那么建立的映射就是：

"a@gmail.com" -> [0, 2]

"b@gmail.com" -> [0]

"c@gmail.com" -> [1, 2]

"d@gmail.com" -> [1]

然后我们还需要一个visited数组，来标记某个账户是否已经被遍历过，0表示为未访问，1表示已访问。在建立好哈希map之后，我们遍历所有的账户，如果账户未被访问过，将其加入队列queue，新建一个集合set，此时进行队列不为空的while循环，取出队首账户，将该该账户标记已访问1，此时将该账户的所有邮箱取出来放入数组mails中，然后遍历mails中的每一个邮箱，将遍历到的邮箱加入集合set中，根据映射来找到该邮箱所属的所有账户，如果该账户未访问，则加入队列中并标记已访问。当while循环结束后，当前账户的所有合并后的邮箱都保存在集合set中，将其转为字符串数组，并且加上用户名在首位置，最后加入结果res中即可

https://www.jianshu.com/p/15a23f2833ca

这个题解法感觉对图的理解很深刻。一开始先不管name, 只处理emails. 把出现在同一个account里面的email都跟该account的第一个email连接，连接的含义是双向的，就是说把彼此存入到自己的neighbors中，本解法里就是map里对应的HashSet<Strings>. 然后用一个visited来保存访问过的email. 遍历account, 每次取出第一个email, 先检查是不是visited, 因为它可能在别的account里不是第一个email而被访问过，如果是的话我们继续访问就会出现重复结果，因为email最后都会被merge到一个账号。如果没有访问过，我们就要做一个bfs, 从该email出发，找它的所有邻居，加到list里。最后要记得sort所有的emails.最后的最后才把名字加到最前面，构成一组答案。为什么从account的第一个email出发做BFS可以找到所有图中于这个email相连的emails呢？因为在该account中不用说，我们建图的时候就连接了所有的emails to 第一个email，那么我们宽搜很快就能得到这些同一个account的email. 同时，这个email可能出现在其他account的非首个email的位置上，而我们建图的时候，连接了它跟这个account的首个email，那么我们把这个首个email放进queue里面之后，一定能访问到所有跟它连接的在该account里的emails, 所以这个account里的所有emails也可以访问到。因此我们从这个account的第一个email出发做宽搜，一定是找得到所有跟它相连的emails的。

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> res = new ArrayList<>();
        Map<String, Set<String>> map = new HashMap<>();
        for (List<String> account : accounts){
            for (int i = 1; i < account.size(); i++){
                if (!map.containsKey(account.get(i))){
                    map.put(account.get(i), new HashSet<String>());
                }    
                map.get(account.get(i)).add(account.get(1));
                map.get(account.get(1)).add(account.get(i));
            }
        }
        Set<String> visited = new HashSet<>();
        for (List<String> account : accounts){
            if (!visited.contains(account.get(1))){
                List<String> list = new ArrayList<>();
                bfs(map, account.get(1), visited, list);
                Collections.sort(list);
                list.add(0, account.get(0));
                res.add(list);
            }
        }
        return res;
    }
    
    private void bfs(Map<String, Set<String>> map, String s, Set<String> visited, List<String> list){
        Queue<String> queue = new LinkedList<>();
        queue.offer(s);
        visited.add(s);
        while (!queue.isEmpty()){
            String curt = queue.poll();
            list.add(curt);
            for (String nei : map.get(curt)){
                if (!visited.contains(nei)){
                    queue.offer(nei);
                    visited.add(nei);
                }
            }
        }
    }
}

X. DFS
https://leetcode.com/problems/accounts-merge/discuss/109158/Java-Solution-(Build-graph-%2B-DFS-search)

Basicly, this is a graph problem. Notice that each account[ i ] tells us some edges. What we have to do is as follows:

1. Use these edges to build some components. Common email addresses are like the intersections that connect each single component for each account.
2. Because each component represents a merged account, do DFS search for each components and add into a list. Before add the name into this list, sort the emails. Then add name string into it.

Examples: Assume we have three accounts, we connect them like this in order to use DFS.
{Name, 1, 2, 3} => Name -- 1 -- 2 -- 3
{Name, 2, 4, 5} => Name -- 2 -- 4 -- 5 (The same graph node 2 appears)
{Name, 6, 7, 8} => Name -- 6 -- 7 -- 8
(Where numbers represent email addresses).

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Set<String>> graph = new HashMap<>();  //<email node, neighbor nodes>
        Map<String, String> name = new HashMap<>();        //<email, username>
        // Build the graph;
        for (List<String> account : accounts) {
            String userName = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                if (!graph.containsKey(account.get(i))) {
                    graph.put(account.get(i), new HashSet<>());
                }
                name.put(account.get(i), userName);
                
                if (i == 1) continue;
                graph.get(account.get(i)).add(account.get(i - 1));
                graph.get(account.get(i - 1)).add(account.get(i));
            }
        }
        
        Set<String> visited = new HashSet<>();
        List<List<String>> res = new LinkedList<>();
        // DFS search the graph;
        for (String email : name.keySet()) {
            List<String> list = new LinkedList<>();
            if (visited.add(email)) {
                dfs(graph, email, visited, list);
                Collections.sort(list);
                list.add(0, name.get(email));
                res.add(list);
            }
        }
        
        return res;
    }
    
    public void dfs(Map<String, Set<String>> graph, String email, Set<String> visited, List<String> list) {
        list.add(email);
        for (String next : graph.get(email)) {
            if (visited.add(next)) {
                dfs(graph, next, visited, list);
            }
        }
    }

http://blogapp.sina.cn/html/share.d.html?vt=4&wm=3049_b111&cid=169938&articleId=6dad631f0102x858
1.
遍历所有user的email_set，检查是否和哈希表[user]列表有交集，如果有交集则融入到email_set，没交集的加入到一个tmp_list里；最后把email_set加入到tmp_list，更新哈希表[user]=tmp_list；
时间复杂度：O（#names * #people of same name * 集合操作）
空间复杂度：O（#total emails）
解法二：UNION-FIND
1. 哈希表email_to_group记录每个email对应的组号
2. 遍历groups，用gset记录email_set里面包含哪些组号（如果还没有分配则赋予counter）；
3.
如果gset包含多个元素，则进行批量的union操作更新email_to_group：组号在gset里面的都更新为相同的一个
4. email_to_group转化生成group_to_email_list
5. 扫描groups获取group_to_name的映射（只需扫描name的第一个email）
6. 根据4和5生成最后结果
时间复杂度：O（#total emails * #total emails）
空间复杂度：O（#total emails）
解法三：union-find+hashtable
解法二的基础上，增加哈希表name_to_email，以便减少union-find对属于某个组之email的查找空间
时间复杂度：O（#total emails * #emails of same name）
空间复杂度：O（#total emails）
解法四：union-find优化查找
0. email_to_group数组存储每个email的父节点，初始化为自身的索引
1. find操作：递归直到找到根节点（groups[x]==x）
2. union操作：email_to_group[find(x)]= email_to_group[y]
3.
遍历accounts时只需要对name下的email_set中，第一个email和其他email形成的对进行union操作
4. 遍历accounts时记录email_to_name
4. 把email_to_group转化为group_to_emails为最后结果
时间复杂度：O（#total emails * log(#total emails)）
空间复杂度：O（#total emails）
解法五：bfs
1. 把email看做点，同一个集合里的email对看做存在一条边，构造图（注意集合里没有边的也要记录点）
2. 原问题转化为求图有几个连通分量
3. 同一个连通分量使用bfs遍历
时间复杂度: O(2 * #total emails)
空间复杂度：O(#total emails)
(忽略排序复杂度)