fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class DSU {
  5. private:
  6.     vector<int> parent;
  7. 	vector<int> sizes;
  8.  
  9. public:
  10.     DSU(int n) : parent(n), sizes(n, 1) {
  11.         for (int i = 0; i < n; i++) {
  12.             parent[i] = i;
  13.         }
  14.     }
  15.  
  16.     int find(int i) {
  17.         if (i == parent[i]) return i;
  18.         return parent[i] = find(parent[i]);
  19.     }
  20.  
  21.     void merge(int u, int v) {
  22.         int ultimateParentU = find(u);
  23.         int ultimateParentV = find(v);
  24.         if (ultimateParentU == ultimateParentV) return;
  25.         if (sizes[ultimateParentU] < sizes[ultimateParentV]) {
  26.             parent[ultimateParentU] = ultimateParentV;
  27.             sizes[ultimateParentV] += sizes[ultimateParentU];
  28.         } else {
  29.             parent[ultimateParentV] = ultimateParentU;
  30.             sizes[ultimateParentU] += sizes[ultimateParentV];
  31.         }
  32.     }
  33. };
  34.  
  35. vector<string> reduceQueries(vector<vector<string>>& synonyms, vector<string>& queries) {
  36.     unordered_set<string> set;
  37.     unordered_map<string, int> map;
  38.     unordered_map<int, string> reverseMap;
  39.     int count = 0;
  40.     for (const auto& s : synonyms) {
  41.         set.insert(s[0]);
  42.         set.insert(s[1]);
  43.         if (!map.count(s[0])) {
  44.             map[s[0]] = count;
  45.             reverseMap[count] = s[0];
  46.             count++;
  47.         }
  48.         if (!map.count(s[1])) {
  49.             map[s[1]] = count;
  50.             reverseMap[count] = s[1];
  51.             count++;
  52.         }
  53.     }
  54.  
  55.     int n = set.size();
  56.     DSU dsu(n);
  57.     for (const auto& s : synonyms) {
  58.         dsu.merge(map[s[0]], map[s[1]]);
  59.     }
  60.  
  61.     unordered_map<string, string> mapper;
  62.     unordered_map<string, int> uniques;
  63.  
  64.     for (const auto& s : queries) {
  65.         vector<string> splitted;
  66.         string word;
  67.         for (char c : s) {
  68.             if (c == ' ') {
  69.                 splitted.push_back(word);
  70.                 word.clear();
  71.             } else {
  72.                 word += c;
  73.             }
  74.         }
  75.         splitted.push_back(word);
  76.  
  77.         string u = splitted[0];
  78.         string v = splitted[1];
  79.         int parentU = dsu.find(map[u]);
  80.         int parentV = dsu.find(map[v]);
  81.         string first = reverseMap[parentU];
  82.         string second = reverseMap[parentV];
  83.         string newQuery = first + " " + second;
  84.         mapper[s] = newQuery;
  85.         uniques[newQuery] = 1;
  86.     }
  87.  
  88.     vector<string> answer;
  89.  
  90.     for (const auto& s : queries) {
  91.         if (uniques.count(mapper[s])) {
  92.             answer.push_back(s);
  93.             uniques[mapper[s]]--;
  94.             if (uniques[mapper[s]] == 0) {
  95.                 uniques.erase(mapper[s]);
  96.             }
  97.         }
  98.     }
  99.  
  100.     return answer;
  101. }
  102.  
  103. int main() {
  104.     vector<vector<string>> synonyms = {{"get", "bring"}, {"water", "liquid"}, {"bring", "nothing"}};
  105.     vector<string> queries = {"get water", "bring water", "get liquid", "bring get"};
  106.  
  107.     vector<string> reducedQueries = reduceQueries(synonyms, queries);
  108.     cout << "Reduced Queries:";
  109.     for (const auto& query : reducedQueries) {
  110.         cout << " " << query;
  111.     }
  112.     cout << endl;
  113.  
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Reduced Queries: get water bring get
https://ideone.com/RC47Qw
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!