Интересная задача на графы - C++ - Ответ 7448145

#include <iostream>
#include <vector>
#include <string>
 
class Graph
{
public:
    Graph() : root(new Node(0)) {}
    void push(std::string const& rhs)
    {
        root->push(rhs);
    }
    int count() const
    {
        return root->count();
    }
    ~Graph()
    {
        delete root; root = 0;
    }
private:
    struct Node
    {
        Node(char const rhs) : c(rhs){}
        void push(std::string const& rhs)
        {
            int j;
            for(j = 0; j < vec.size(); ++j)
            {
                if(vec[j]->c == rhs[0]) break;
            }
            if(j == vec.size())
            {
                vec.push_back(new Node(rhs[0]));
                if(rhs.size() > 1) vec.back()->push(rhs.substr(1));
            }
            else if(rhs.size() > 1) vec[j]->push(rhs.substr(1));
        }
        int count() const
        {
            int res = 1;
            for(int i = 0; i < vec.size(); ++i)
            {
                res += vec[i]->count();
            }
            return res;
        }
        ~Node()
        {
            for(int i = 0; i < vec.size(); ++i)
            {
                delete vec[i]; vec[i] = 0;
            }
        }
 
        char c;
        std::vector<Node*> vec;
    };
 
    Node* root;
 
    Graph(Graph const&);
    Graph& operator=(Graph);
};
 
int main()
{
    Graph g;
 
    g.push("cat");
    g.push("more");
    g.push("car");
    g.push("clear");
 
    std::cout << g.count() << "\n\n";
    return 0;
}