Leetcode|并查集+哈希表|721. 账户合并

class UnionFind {
public:
    int count;
    vector<int> parent, size;

    UnionFind(int n) {
        count = n;
        parent.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    void unite(int a, int b) {
        int rootA = find_root(a);
        int rootB = find_root(b);
        if (rootA == rootB) return;
        if (size[rootA] < size[rootB]) {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        } else {
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        count--;
    }

    bool connected(int a, int b) {
        int rootA = find_root(a);
        int rootB = find_root(b);
        return rootA == rootB;
    }

    int find_root(int node) {
        while (parent[node] != node) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }
        return node;
    }
};

class Solution {
public:
    // 存储已去重的<邮箱, id> 不同邮箱可能对应的相同人
    unordered_map<string, int> email2id;
    // 存储<id, 邮箱列表> 同一人对应的未排序所有邮箱列表
    unordered_map<int, vector<string>> id2email_list;
    vector<vector<string>> res;

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int size = accounts.size();
        UnionFind uf(size);
        // 1.遍历每个邮箱，并查集将相同邮箱对应的不同ID进行合并，存储已去重<邮箱, id>
        for (int i = 0; i < size; i++) 
            for (int j = 1; j < accounts[i].size(); j++) {
                if (email2id.count(accounts[i][j])) 
                    uf.unite(email2id[accounts[i][j]], i);
                else
                    email2id[accounts[i][j]] = i;
            }
        // 2.遍历已去重<邮箱, id>，利用并查集的find_root功能找出不同邮箱对应的相同人ID，然后合并到<id, 邮箱列表>中
        for (auto& [email, id] : email2id) {
            int rootID = uf.find_root(id);
            id2email_list[rootID].push_back(email);
        }
        // 3.遍历<id, 邮箱列表>并排序，逐个加入到结果中
        for (auto& [id, email_list] : id2email_list) {
            vector<string> item(1, accounts[id][0]);
            sort(email_list.begin(), email_list.end());
            for (auto& email : email_list) item.push_back(email);
            res.push_back(item);
        }
        return res;
    }
};