nikunjsoni

721

Nov 28th, 2021
476
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     struct UnionFind {
  4.         UnionFind(const int n)
  5.             : parent(n), rank(n, 1) {
  6.                 for (int i = 0 ; i < n ; ++i)
  7.                     parent[i] = i;
  8.             }
  9.        
  10.         int find(int u) {
  11.             if (u == parent[u]) return u;
  12.             return parent[u] = find(parent[u]);
  13.         }
  14.        
  15.         void merge(int u, int v) {
  16.             u = find(u);
  17.             v = find(v);
  18.             if (u == v) return;
  19.             if (rank[u] > rank[v]) swap(u, v);
  20.             parent[u] = v;
  21.             if (rank[u] == rank[v]) ++rank[v];
  22.         }
  23.        
  24.         vector<int> parent;
  25.         vector<int> rank;
  26.     };
  27.    
  28.     vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
  29.         const int n = accounts.size();
  30.         unordered_map<string, int> emailMapping;
  31.         UnionFind uf {n};
  32.        
  33.         int user = 0;
  34.         for (auto& a : accounts) {
  35.             for (int i = 1 ; i < a.size() ; ++i) {
  36.                 auto it = emailMapping.find(a[i]);
  37.                 if (it == emailMapping.end())
  38.                     emailMapping[a[i]] = user;
  39.                 else
  40.                     uf.merge(user, it->second);
  41.             }
  42.             ++user;
  43.         }
  44.        
  45.         vector<vector<string>> res (n, vector<string> {""});
  46.         for (auto& p : emailMapping) {
  47.             const int userId = uf.find(p.second);
  48.             res[userId].emplace_back(string {p.first});
  49.         }  // End for
  50.        
  51.         int i = 0, j = 0;
  52.         while (i < n) {
  53.             if (res[i].size() > 1) {
  54.                 sort(res[i].begin(), res[i].end());
  55.                 res[i][0] = accounts[i][0];
  56.                 swap(res[i], res[j++]);
  57.             }
  58.             ++i;
  59.         }
  60.         res.resize(j);
  61.         return res;
  62.     }
  63. };
RAW Paste Data