Time Cost

37min19s

Implementation

None

Code

• Solution ```c++ class Solution { unordered_map<string, string> parent; unordered_map<string, int> rank_;

  string findSet(const string& s) { auto it = parent.find(s); if (it == parent.end()) { parent[s] = s; rank_[s] = 0; return s; } if (parent[s] != s) parent[s] = findSet(parent[s]); return parent[s]; }

  void join(const string& a, const string& b) { string rootA = findSet(a), rootB = findSet(b); if (rootA == rootB) return;

    if (rank_[rootA] > rank_[rootB]) parent[rootB] = rootA;
    else if (rank_[rootA] < rank_[rootB]) parent[rootA] = rootB;
    else {
        parent[rootB] = rootA;
        rank_[rootA]++;
    }   }
  

public:

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, string> emailToName;

    // 1) Union emails within the same account
    for (auto& acc : accounts) {
        const string& name = acc[0];
        if (acc.size() < 2) continue;

        const string& firstEmail = acc[1];
        findSet(firstEmail);                 
        emailToName[firstEmail] = name;

        for (int i = 2; i < (int)acc.size(); ++i) {
            const string& email = acc[i];
            findSet(email);                  
            emailToName[email] = name;       
            join(firstEmail, email);
        }
    }

    // 2) Group emails by root
    unordered_map<string, vector<string>> groups;
    groups.reserve(parent.size() * 2);

    for (auto& kv : parent) {
        const string& email = kv.first;
        string root = findSet(email);
        groups[root].push_back(email);
    }

    // 3) Build result: sort emails, prepend name
    vector<vector<string>> res;
    res.reserve(groups.size());

    for (auto& kv : groups) {
        auto& emails = kv.second;
        sort(emails.begin(), emails.end());

        vector<string> merged;
        merged.reserve(emails.size() + 1);

        // name can be taken from any email in the group
        merged.push_back(emailToName[emails[0]]);
        merged.insert(merged.end(), emails.begin(), emails.end());

        res.push_back(std::move(merged));
    }

    return res; 
} }; ```