721. 账户合并

题目链接：

https://leetcode.cn/problems/accounts-merge/description/?envType=daily-question&envId=2024-07-15

题目描述：

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

示例 1：

输入：accounts = [[“John”, “johnsmith@mail.com”, “john00@mail.com”], [“John”, “johnnybravo@mail.com”], [“John”, “johnsmith@mail.com”, “john_newyork@mail.com”], [“Mary”, “mary@mail.com”]]
输出：[[“John”, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’], [“John”, “johnnybravo@mail.com”], [“Mary”, “mary@mail.com”]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 “johnsmith@mail.com”。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [[‘Mary’，‘mary@mail.com’]，[‘John’，‘johnnybravo@mail.com’]，
[‘John’，‘john00@mail.com’，‘john_newyork@mail.com’，‘johnsmith@mail.com’]] 也是正确的。
示例 2：

输入：accounts = [[“Gabe”,“Gabe0@m.co”,“Gabe3@m.co”,“Gabe1@m.co”],[“Kevin”,“Kevin3@m.co”,“Kevin5@m.co”,“Kevin0@m.co”],[“Ethan”,“Ethan5@m.co”,“Ethan4@m.co”,“Ethan0@m.co”],[“Hanzo”,“Hanzo3@m.co”,“Hanzo1@m.co”,“Hanzo0@m.co”],[“Fern”,“Fern5@m.co”,“Fern1@m.co”,“Fern0@m.co”]]
输出：[[“Ethan”,“Ethan0@m.co”,“Ethan4@m.co”,“Ethan5@m.co”],[“Gabe”,“Gabe0@m.co”,“Gabe1@m.co”,“Gabe3@m.co”],[“Hanzo”,“Hanzo0@m.co”,“Hanzo1@m.co”,“Hanzo3@m.co”],[“Kevin”,“Kevin0@m.co”,“Kevin3@m.co”,“Kevin5@m.co”],[“Fern”,“Fern0@m.co”,“Fern1@m.co”,“Fern5@m.co”]]

解析：

并查集

1. 首先，因为邮箱是专属于某一个人的，但是它会重复出现，所以我们对每个首次出现的邮箱，赋予ID和名字，赋予ID的同时记录下邮箱的数量emailsCount，这里用 emailToIndex 表示**“邮箱——ID”，用 emailToName 表示“邮箱——名字”**。

2. 初始化并查集，用邮箱数量作为并查集的大小来进行初始化，因为是想要把邮箱进行合并。

3. 合并并查集，之前对每个邮箱都赋有一个ID，把属于同一个人的ID合并到一起
   1）不同ID在同一个人后面出现，属于一个人，合并;
   2）同一ID在不同的人后面出现，属于一个人，合并

4. 用 indexToEmails 表示**“ID——邮箱”，根据 emailToIndex 找到每个邮箱对应的ID，然后用find函数找到ID对应的并查集中的根ID**，把该邮箱加入到根ID的邮箱中，即加入到 indexToEmails 中。

5. 在**“ID——邮箱”里（ indexToEmails ），把邮箱排序**，然后在 emailToName 中利用邮箱找到名字，最后把名字和排序后的邮箱放到答案中

代码：

class Solution {
    vector<int> parent;
    int find(int x)
    {
        if(parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        map<string , int> emailToIndex;   //邮箱对应编号
        map<string , string> emailToName; //邮箱对应名字
        int emailsCount = 0;
        for(auto& account : accounts){
            string& name = account[0];     //名字
            int size = account.size();
            for(int i = 1 ; i < size ; i++){
                string& email = account[i];
                if(!emailToIndex.count(email)){//邮箱没有对应编号，即没出现过，给它编号和名字
                    emailToIndex[email] = emailsCount++;
                    emailToName[email] = name;
                }
            }
        }

        //开始并查集，先初始化
        parent.resize(emailsCount);
        for(int i = 0 ; i < emailsCount ; i++)
            parent[i] = i;

        for(auto& account : accounts){  
            //之前对每个邮箱都赋有一个ID，不同ID在同一个人后面出现，合并，属于一个人
            //不同ID在不同的人后面出现，这两个人属于一个人，合并
            string& firstEmail = account[1];
            int firstIndex = emailToIndex[firstEmail];
            int size = account.size();
            for(int i = 2 ; i < size ; i++){
                string& nextEmail = account[i];
                int nextIndex = emailToIndex[nextEmail];
                parent[find(firstIndex)] = find(nextIndex);
            }
        }

        map<int , vector<string>> indexToEmails;  //ID对应邮箱
        for(auto& [email,_] : emailToIndex){
            //根据邮箱找到对应的根ID，然后添加到该ID的邮箱中
            int index = find(emailToIndex[email]);
            vector<string>& account = indexToEmails[index];
            account.emplace_back(email);
            indexToEmails[index] = account;
        }

        vector<vector<string>> merged;  //最终答案
        for(auto& [_,emails] : indexToEmails){
            //在ID对应邮箱里，把邮箱排序，然后把名字和邮箱放到答案中
            sort(emails.begin() , emails.end());
            string& name = emailToName[emails[0]];
            vector<string> account;
            account.emplace_back(name);
            for(auto& email : emails){
                account.emplace_back(email);
            }
            merged.emplace_back(account);
        }
        return merged;
    }
};