[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;
    }
};

접근

같은 이메일을 사용할 경우 두 계정이 같은 사람에게 속하기 때문에 모든 메일들을 살펴보면서 메일 간의 관계를 확인해주었다. 이를 기반으로 같은 메일들을 dfs로 찾아서 추가해 줄 수 있었고 set을 이용해서 이미 확인한 메일도 체크해 주어서 같은 이메일이 여러 번 나올 경우를 차단했다.