fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <assert.h>
  5. using namespace std;
  6.  
  7. class Node{
  8.     public:
  9.     Node * parent;
  10.     vector<Node *> children;
  11.     string key;
  12.     Node(string const & name) : parent(NULL), key(name) {}
  13. };
  14.  
  15. void print_recursive(Node * node, int depth = 0) {
  16. 	for (int d = 0; d < depth; ++d) {
  17. 		cout << "   ";
  18. 	}
  19. 	cout << node->key << endl;
  20.  
  21. 	for (auto & child: node->children) {
  22. 		print_recursive(child, depth + 1);
  23. 	}
  24. }
  25.  
  26.  
  27. class tree{
  28.     public:
  29.     int size;
  30.     Node * root;
  31.     tree() : size(0), root(NULL) {}
  32.  
  33.     Node * find_index(Node * cur, string const & key) {
  34.         if (cur == NULL) {
  35.             return NULL;
  36.         }
  37.         if (cur->key == key){
  38.             return cur;
  39.         }
  40.         for (auto const & child: cur->children) {
  41.             auto result = find_index(child, key);
  42.             if (result != NULL) {
  43.                 return result;
  44.             }
  45.         }
  46.         return NULL;
  47.     }
  48.  
  49.     void  add() { 
  50.     	std::set<Node *> roots;
  51.         string father, son;
  52.         while (cin >> father >> son) {
  53.  
  54.         	Node * nfather = get_node(father, roots);
  55.         	if (nfather->parent == NULL) {
  56.         		roots.insert(nfather);
  57.         	}
  58.  
  59.             Node * nson = get_node(son, roots);
  60.  
  61.             assert(nson->parent == NULL); // nson must not have another father
  62.             nson->parent = nfather;
  63.             nfather->children.push_back(nson);
  64.             roots.erase(nson);
  65.         }
  66.         assert(roots.size() == 1);
  67.         root = *(roots.begin());
  68.     }
  69.  
  70.     // Get or create the node with key name
  71.     Node * get_node(string const & name, set<Node *> const & roots) {
  72.     	Node * cur = NULL;
  73.         for (auto & root: roots) {
  74.         	cur = find_index(root, name);
  75.         	if (cur != NULL) break;
  76.         }
  77.         if (cur == NULL) { // create node if not found
  78.             ++size;
  79.         	cur = new Node(name);
  80.         }
  81.         return cur;
  82.     }
  83. }; 
  84.  
  85. int main() {
  86. 	tree T;
  87. 	T.add();
  88. 	print_recursive(T.root);
  89. }
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
r c
c gc
c gc2
r c2
sr r
stdout
copy 
sr
   r
      c
         gc
         gc2
      c2
https://ideone.com/qkpgB7
language:
C++14 (gcc 8.3)
created:
10 years 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!