力扣721.账户合并

力扣721.账户合并

• 并查集 + dfs

  • 哈希表以地址为下标 存账户下标数组
  • 遍历每个账户下标
  • 其中的每个email如果还对应其他下标(说明两下标对应的账户名称一样 可以合并)
  • 那么继续dfs

•   class Solution {
    public:
        vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
            unordered_map<string,vector<int>> email_to_idx;
            for(int i=0;i<accounts.size();i++)
                for(int k=1;k<accounts[i].size();k++)
                    email_to_idx[accounts[i][k]].push_back(i);
            unordered_set<string> email_set;
            //记录每个下标是否遍历过
            vector<int> vis(accounts.size());
            auto dfs = [&](auto &&dfs,int i) ->void
            {
                vis[i] = true;
                //遍历其中每个地址
                for(int k=1;k<accounts[i].size();k++)
                {
                    string &email = accounts[i][k];
                    if(email_set.contains(email))
                        continue;
                    //没有放进来过 就插入 并看是否有其他下标也包含这个地址
                    email_set.insert(email);
                    for(int j:email_to_idx[email])
                        if(!vis[j])
                            dfs(dfs,j);
                }
            };
            vector<vector<string>> res;
            for(int i=0;i<vis.size();i++)
            {
                //dfs过就continue
                if(vis[i]) 
                    continue;
                email_set.clear();
                dfs(dfs,i);
                //账户名称 + 账户地址的集合(字典序排序) 放入答案
                vector<string> cur = {accounts[i][0]};
                cur.insert(cur.end(),email_set.begin(),email_set.end());
                sort(cur.begin()+1,cur.end());
                res.push_back(cur);
            }
            return res;
        }
    };