721. Accounts Merge

解題思路

這類「誰跟誰是一個小群體」的題目跟 union find 有關，這題額外加上還有 "name" 這一個標示群體名稱的字串。

解題分為四步，

step1: 初始化，每一個 email 的老大(parent)都是自己，並且記錄 email 的擁有者叫甚麼名字。

step2: 透過 find function，把每串除了第一個(本來就指向自己)的其餘的老大都指向第一個。在這個過程中，如果兩串都有同一個 email 出現，那自然會被歸在同一個群體之中(因為老大都一樣)。

step3: 先前只是記錄 email 跟對應的老大是誰。在 step3 要轉成 map 結構，一個老大 string 所屬的擁有者名字會對應到 set of other strings in the same group。做法是 traverse 每一個 email，map[老大].insert(自己)

step4:  依題目要求把 email 們先 sort，接著把名字加入即可。

這題好難，改天再寫一次。

程式碼

class Solution {
public:
    string find(string email, unordered_map<string, string>& parent)
    {
        if(email != parent[email])
            parent[email] = find(parent[email], parent); // compress
        return parent[email];
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, string> owner; // email's owner(email -> name)
        unordered_map<string, string> parent; // email's parent for union
        unordered_map<string, set<string>> unions; // answer

        // Step 1
        for (auto account : accounts) {
            for (int i = 1; i < account.size(); i++) {
                owner[account[i]] = account[0];
                parent[account[i]] = account[i];
            }
        }
        
        // Step 2
        for (auto account : accounts) {
            string p = find(account[1], parent);
            for (int i = 2; i < account.size(); i++) {
                parent[find(account[i], parent)] = p;
            }
        }
        
        // Step 3
        for (auto email : owner) {
            unions[find(email.first, parent)].insert(email.first);
        }
        
        // Step 4
        vector<vector<string>> result;
        for (auto union_ : unions) {
            vector<string> emails(union_.second.begin(), union_.second.end());
            emails.insert(emails.begin(), owner[union_.first]);
            result.push_back(emails);
        }
        return result;

    }
};