paradox64ce

accounts-merge

Aug 13th, 2021
642
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class DSU{
  2.         public:
  3.         vector<int> parent, rank;
  4.         DSU(int n){
  5.             parent.resize(n, -1);
  6.             // iota(parent.begin(), parent.end(), 0);
  7.             rank.resize(n, 1);
  8.         }
  9.        
  10.         int findSet(int x){
  11.             if(parent[x]==-1)
  12.                 return x;
  13.             return parent[x] = findSet(parent[x]);
  14.         }
  15.        
  16.         void unite(int x, int y){
  17.             int px = findSet(x);
  18.             int py = findSet(y);
  19.            
  20.             if(px==py)
  21.                 return;
  22.             if(rank[px] >= rank[py]){
  23.                 swap(px, py);
  24.             }
  25.            
  26.             rank[py] += rank[px];
  27.             parent[px] = py;
  28.         }
  29.        
  30.         int findDistinctSets(){
  31.             int cnt = 0;
  32.             for(int v:parent){
  33.                 cnt += (v==-1);
  34.             }
  35.             return cnt;
  36.         }
  37. };
  38.    
  39. class Solution {
  40. public:
  41.     vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
  42.         int n = accounts.size();
  43.         DSU dsu = DSU(n);
  44.         vector<set<string>> acc(n);
  45.        
  46.         for(int i = 0;i<n;i++){
  47.             for(int j = 1;j<accounts[i].size();j++){
  48.                 acc[i].insert(accounts[i][j]);
  49.             }
  50.         }
  51.        
  52.         for(int i = 0; i<n ;i++){ // 1000
  53.             for(int j = 0;j<i;j++){ // 1000
  54.                 for(int k = 1;k<accounts[i].size();k++){ // 10
  55.                     if(acc[j].count(accounts[i][k])){ // 10 log ()
  56.                         dsu.unite(i, j);
  57.                         break;
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.        
  63.         for(int i = 0;i<n;i++){
  64.             dsu.findSet(i);
  65.         }
  66.        
  67.         unordered_map<int, set<string>> mp;
  68.        
  69.         for(int i = 0;i<n;i++){
  70.             int id = dsu.findSet(i);
  71.             if(mp.find(id)==mp.end()){
  72.                 mp[id] = set<string>();
  73.             }
  74.            
  75.             for(int j = 1;j<accounts[i].size();j++){
  76.                 mp[id].insert(accounts[i][j]);
  77.             }
  78.         }
  79.        
  80.         vector<vector<string>> ans;
  81.         for(auto e:mp){
  82.             vector<string> t;
  83.             t.push_back(accounts[e.first][0]);
  84.             for(auto s:e.second){
  85.                 t.push_back(s);
  86.             }
  87.             ans.push_back(t);
  88.         }
  89.        
  90.         // cout<<mp.size()<<"\n";
  91.        
  92.         return ans;
  93.     }
  94. };
RAW Paste Data