Advertisement
Josif_tepe

Untitled

Mar 17th, 2024
428
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     vector<int> idx, sz;
  4.     int find_root(int A) {
  5.         while(A != idx[A]) {
  6.             idx[A] = idx[idx[A]];
  7.             A = idx[A];
  8.         }
  9.         return A;
  10.     }
  11.     void merge_two_rots(int A, int B) {
  12.         int root_a = find_root(A);
  13.         int root_b = find_root(B);
  14.         if(root_a == root_b) {
  15.             return;
  16.         }
  17.         if(sz[root_a] < sz[root_b]) {
  18.             idx[root_a] = idx[root_b];
  19.             sz[root_b] += sz[root_a];
  20.         }
  21.         else {
  22.             idx[root_b] = idx[root_a];
  23.             sz[root_a] += sz[root_b];
  24.         }
  25.     }
  26.    
  27.     vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
  28.         int n = accounts.size();
  29.         idx.resize(n);
  30.         sz.resize(n);
  31.         for(int i = 0; i < n; i++) {
  32.             idx[i] = i;
  33.             sz[i] = 1;
  34.         }
  35.         for(int i = 0; i < n; i++) {
  36.             for(int j = 1; j < accounts[i].size(); j++) {
  37.                 for(int k = 0; k < n; k++) {
  38.                     if(i != k) {
  39.                         if(accounts[i][0] == accounts[k][0]) {
  40.                             for(int l = 1; l < accounts[k].size(); l++) {
  41.                                 if(accounts[i][j] == accounts[k][l]) {
  42.                                     merge_two_rots(i, k);
  43.                                     break;
  44.                                 }
  45.                             }
  46.                         }
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.         map<int, vector<string>> mapa;
  52.         for(int i = 0; i < n; i++) {
  53.             int root = find_root(i);
  54.             for(int j = 0; j < accounts[i].size(); j++) {
  55.                 mapa[root].push_back(accounts[i][j]);
  56.             }
  57.         }
  58.         vector<vector<string>> res;
  59.         for(map<int, vector<string>>::iterator it = mapa.begin(); it != mapa.end(); it++) {
  60.             set<string> st;
  61.             for(int i = 0; i < it->second.size(); i++) {
  62.                 if(it->second[i] != it->second[0]) {
  63.                     st.insert(it->second[i]);
  64.                 }
  65.             }
  66.             vector<string> vv;
  67.             vv.push_back(it->second[0]);
  68.             for(set<string>::iterator it2 = st.begin(); it2 != st.end(); it2++) {
  69.                 vv.push_back(*it2);
  70.             }
  71.             res.push_back(vv);
  72.         }
  73.         return res;
  74.     }
  75. };
  76.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement