原题地址（中等）

方法1—并查集+哈希表

思路

见力扣题解，写的真的好棒~

代码

// 并查集模板
class UnionFind {
public:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int _n): parent(vector<int>(_n)), rank(vector<int>(_n)) {
        for(int i=0; i<_n; i++) 
            parent[i] = i;
    }
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);  // 路径压缩
        }
        return parent[x];
    }
    void merge(int x, int y) {  // 按秩合并
        int rootx = find(x);
        int rooty = find(y);
        if(rootx != rooty) {
            if(rank[rootx] < rank[rooty])   swap(rootx, rooty);
            parent[rooty] = rootx;
            if(rank[rootx] == rank[rooty])  rank[rootx]++;
        }
    }
};
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string> > res;
        // 作用：存储每个邮箱属于哪个账户 ，同时 在遍历邮箱时，判断邮箱是否出现过
        // 格式：<邮箱，账户id>
        unordered_map<string, int> um;
        int n = accounts.size();
        UnionFind uf(n);
        for(int i = 0; i < n; i++) {
            int m = accounts[i].size();
            // 对每个邮箱，如果还未出现过，就放到哈希表中，否则将该账户与已经出现过该邮箱的账户合并
            for(int j = 1; j < m; j++) {
                string s = accounts[i][j];
                if(um.find(s) == um.end())  um[s] = i;
                else    uf.merge(i, um[s]);
            }
        }
        // 作用： 存储每个账户下的邮箱
        // 格式： <账户id, 邮箱列表> >
        // 注意：umv的key必须是账户id，不能是账户名称，名称可能相同，会造成覆盖
        unordered_map<int, vector<string>> umv;
        for(auto& [k, v] : um)  umv[uf.find(v)].emplace_back(k);
        for(auto& [k, v] : umv) {
            sort(v.begin(), v.end());
            vector<string> tmp(1, accounts[k][0]); // 名字
            tmp.insert(tmp.end(), v.begin(), v.end());
            res.emplace_back(tmp);
        }
        return res;
    }
};