SHARE
TWEET

Untitled

a guest Feb 19th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <map>
  6.  
  7.  
  8. class Graph{
  9. public:
  10.     void new_word(const std::string& word) {
  11.         Vertex* prev = nullptr;
  12.         std::string temp = "aaa";
  13.         for(size_t i = 0; i < word.size() - 2; ++i) {
  14.             temp[0] = word[i];
  15.             temp[1] = word[i + 1];
  16.             temp[2] = word[i + 2];
  17.  
  18.             if(vertexes_.find(temp) == vertexes_.end()) {
  19.                 auto v_new = new Vertex(temp);
  20.                 vertexes_.emplace(temp, v_new);
  21.                 if(prev != nullptr) {
  22.                     prev->addEdge(v_new);
  23.                 }
  24.                 prev = v_new;
  25.             }
  26.             else {
  27.                 if(prev != nullptr) {
  28.                     prev->addEdge(vertexes_[temp]);
  29.                 }
  30.                 prev = vertexes_[temp];
  31.             }
  32.         }
  33.     }
  34.  
  35.     void print_size() {
  36.         std::cout << vertexes_.size() << std::endl;
  37.     }
  38.  
  39.     void print_edges() {
  40.         std::vector<Vertex::Edge*> edges;
  41.         for(auto v: vertexes_) {
  42.             for(auto e: v.second->edges) {
  43.                 edges.push_back(e);
  44.             }
  45.         }
  46.  
  47.         std::cout << edges.size() << std::endl;
  48.         for(auto e: edges) {
  49.             std::cout << e->begin->triple << ' ' << e->end->triple << ' ' << e->count << std::endl;
  50.         }
  51.     }
  52. private:
  53.     struct Vertex{
  54.         struct Edge{
  55.             Vertex* begin;
  56.             Vertex* end;
  57.             size_t count;
  58.  
  59.             Edge() = default;
  60.         };
  61.  
  62.         std::string triple;
  63.         std::vector<Edge*> edges;
  64.  
  65.         Vertex() = default;
  66.         explicit Vertex(const std::string& word): triple(word)
  67.         {}
  68.  
  69.         void addEdge(Vertex* end) {
  70.             size_t it = 0;
  71.             for(; it < edges.size(); it++) {
  72.                 if(edges[it]->end == end) {
  73.                     break;
  74.                 }
  75.             }
  76.             if(it == edges.size()) {
  77.                 auto e = new Edge{this, end, 1};
  78.                 edges.push_back(e);
  79.             }
  80.             else{
  81.                 edges[it]->count++;
  82.             }
  83.         }
  84.     };
  85.  
  86.     std::map<std::string, Vertex*> vertexes_;
  87. };
  88.  
  89.  
  90. int main() {
  91.     int n;
  92.     std::cin >> n;
  93.     std::string input;
  94.     Graph g;
  95.  
  96.     for(int i = 0; i < n; ++i) {
  97.         std::cin >> input;
  98.         g.new_word(input);
  99.     }
  100.  
  101.     g.print_size();
  102.     g.print_edges();
  103. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top