737

class Solution {
public:
    bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<vector<string>>& pairs) {
        if(words1.size() != words2.size()) return false;
        unordered_map<string, string> m;
        for(auto p: pairs){
            string p1 = find(m, p[0]);
            string p2 = find(m, p[1]);
            if(p1 != p2)
                m[p1] = p2;
        }

        for(int i=0; i<words1.size(); i++)
            if(find(m, words1[i]) != find(m, words2[i]))
                return false;

        return true;
    }

    string find(unordered_map<string, string> &m, string word){
        if(!m.count(word))
            m[word] = word;
        return (m[word] == word) ? word : (m[word] = find(m, m[word]));
    }
};