fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <sstream>
  5. #include <set>
  6. #include <algorithm>
  7.  
  8. static int NowSeqS = 0;
  9.  
  10. struct StrSeq {
  11.   std::string str;
  12.   int index;
  13.   StrSeq(std::string s) : str(s), index(-1) {}
  14. };
  15.  
  16. bool operator<(StrSeq a, StrSeq b) { return a.str < b.str; }
  17.  
  18. std::ostream &operator<<(std::ostream &s, StrSeq ob) {
  19.   s << ob.str;
  20.   return s;
  21. }
  22.  
  23. void set_grouping(std::vector<StrSeq> &input, std::vector<std::vector<StrSeq>> &output) {
  24.   std::vector<std::set<StrSeq> *> sets;
  25.   for (auto &s : input) {
  26.     std::string g1x, g2x;
  27.     std::stringstream ss(s.str);
  28.     getline(ss, g1x, '=');
  29.     getline(ss, g2x);
  30.     StrSeq g1 = StrSeq(g1x);
  31.     StrSeq g2 = StrSeq(g2x);
  32.     /*-------------------------------------*/
  33.     std::set<StrSeq> *g1_in_set = nullptr;
  34.     std::set<StrSeq> *g2_in_set = nullptr;
  35.     /* g1 */
  36.     for (auto p : sets) {
  37.       auto q = (*p).find(g1);
  38.       if (q != (*p).end())
  39.         g1_in_set = p;
  40.     }
  41.     /* g2 */
  42.     for (auto p : sets) {
  43.       auto q = (*p).find(g2);
  44.       if (q != (*p).end()) {
  45.         if (g1_in_set == p)
  46.           continue;
  47.         g2_in_set = p;
  48.       }
  49.  
  50.     }
  51.     /*-------------------------------------*/
  52.     if (g1_in_set == nullptr && g2_in_set == nullptr) {
  53.       g1.index = NowSeqS++;
  54.       g2.index = NowSeqS++;
  55.       std::set<StrSeq> *p = new std::set<StrSeq>();
  56.       (*p).insert(g1);
  57.       (*p).insert(g2);
  58.       sets.push_back(p);
  59.     } else if (g1_in_set != nullptr && g2_in_set == nullptr) {
  60.       g2.index = NowSeqS++;      
  61.       (*g1_in_set).insert(g2);
  62.     } else if (g1_in_set == nullptr && g2_in_set != nullptr) {
  63.       g1.index = NowSeqS++;
  64.       (*g2_in_set).insert(g1);
  65.     } else if (g1_in_set != g2_in_set) {
  66.       for (auto g : *g2_in_set)
  67.         (*g1_in_set).insert(g);
  68.       for (auto p = sets.begin(); p != sets.end(); p++) {
  69.         if (*p == g2_in_set) {
  70.           sets.erase(p);
  71.           break;
  72.         }
  73.       }
  74.     }
  75.   }
  76.   /*-------------------------------------*/
  77.   std::vector<StrSeq> set_contents;
  78.   for (auto p : sets) {
  79.     for (auto g_string : *p) { /* *p == std::set */
  80.       set_contents.push_back(g_string);
  81.     }
  82.     output.push_back(set_contents);
  83.     set_contents.clear();
  84.   }      
  85.  
  86.   for (auto p : sets)
  87.     delete p;
  88. }
  89.  
  90. int main() {
  91.   std::vector<std::string> input = {
  92.     "a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
  93.     "a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
  94.     "b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3" };
  95.   std::vector<std::vector<StrSeq>> output;
  96.  
  97.   std::vector<StrSeq> input2;
  98.   for (auto s : input)
  99.     input2.push_back(StrSeq(s));
  100.  
  101.   set_grouping(input2, output);
  102.  
  103.   for (auto &v : output) {
  104.     sort(v.begin(), v.end(), [](auto const &lhs, auto const &rhs) {
  105.       return lhs.index < rhs.index;
  106.     });
  107.     std::cout << "{ ";
  108.     for (auto s : v) {
  109.       std::cout << "\"" << s << "\", ";
  110.     }
  111.     std::cout << "}" << std::endl;
  112.   }
  113.   return 0;
  114. }
  115. /* end */
  116.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{ "a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4", }
{ "e1", "e2", "e3", }
{ "c1", "c2", "c3", "c4", "d1", "d2", "d3", }
https://ideone.com/A2H5zg
language:
C++14 (clang 8.0)
created:
91 days ago
visibility:
secret

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!