accounts-merge

class DSU{
        public:
        vector<int> parent, rank;
        DSU(int n){
            parent.resize(n, -1);
            // iota(parent.begin(), parent.end(), 0);
            rank.resize(n, 1);
        }

        int findSet(int x){
            if(parent[x]==-1)
                return x;
            return parent[x] = findSet(parent[x]);
        }

        void unite(int x, int y){
            int px = findSet(x);
            int py = findSet(y);

            if(px==py)
                return;
            if(rank[px] >= rank[py]){
                swap(px, py);
            }

            rank[py] += rank[px];
            parent[px] = py;
        }

        int findDistinctSets(){
            int cnt = 0;
            for(int v:parent){
                cnt += (v==-1);
            }
            return cnt;
        }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        DSU dsu = DSU(n);
        vector<set<string>> acc(n);

        for(int i = 0;i<n;i++){
            for(int j = 1;j<accounts[i].size();j++){
                acc[i].insert(accounts[i][j]);
            }
        }

        for(int i = 0; i<n ;i++){ // 1000
            for(int j = 0;j<i;j++){ // 1000
                for(int k = 1;k<accounts[i].size();k++){ // 10
                    if(acc[j].count(accounts[i][k])){ // 10 log ()
                        dsu.unite(i, j);
                        break;
                    }
                }
            }
        }

        for(int i = 0;i<n;i++){
            dsu.findSet(i);
        }

        unordered_map<int, set<string>> mp;

        for(int i = 0;i<n;i++){
            int id = dsu.findSet(i);
            if(mp.find(id)==mp.end()){
                mp[id] = set<string>();
            }

            for(int j = 1;j<accounts[i].size();j++){
                mp[id].insert(accounts[i][j]);
            }
        }

        vector<vector<string>> ans;
        for(auto e:mp){
            vector<string> t;
            t.push_back(accounts[e.first][0]);
            for(auto s:e.second){
                t.push_back(s);
            }
            ans.push_back(t);
        }

        // cout<<mp.size()<<"\n";

        return ans;
    }
};