[Leetcode] 721. Accounts Merge (C++)


質問する


721. Accounts Merge

コード#コード#

class Solution {
public:
    unordered_set<string> visited;
    unordered_map<string, vector<string>> adj;
    
    void dfs(vector<string>& merged, string& email){
        visited.insert(email);
        
        merged.push_back(email);
        
        for (auto a : adj[email]){
            if (visited.find(a) != visited.end()) continue;
            dfs(merged, a);
        }
    }
    
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        for (auto account : accounts){
            int sz = account.size();
            
            for (int i = 2; i < sz; i++){
                adj[account[1]].push_back(account[i]);
                adj[account[i]].push_back(account[1]);
            }
        }
        
        vector<vector<string>> merged;
        for (auto account : accounts){
            string name = account[0];
            string first = account[1];
            
            if (visited.find(first) == visited.end()){
                vector<string> temp;
                temp.push_back(name);
                dfs(temp, first);
                sort(temp.begin()+1, temp.end());
                merged.push_back(temp);
            }
        }
        
        return merged;
    }
};

に近づく


同じメールを使用する場合、2つのアカウントが同じ人に属しているため、すべてのメールを表示し、メール間の関係を確認しました.これに基づいて、dfsで同じメールを検索して追加したり、setを使用して確認したメールをチェックしたりして、同じメールが複数回発生することを防止することができます.