Оптимизировать задачу на графы

[Dmitry_DM]

Здравствуйте! Вот сделал одну задачу олимпиадного уровня, и в системе проверки на 4 тесте вылетает с ошибкой "лимит памяти" (больше 3000кб)
помогите, подскажите, как оптимизировать алгоритм, или поменять способ прохода по дереву, что бы памяти "ело" меньше.
Дан набор слов. Требуется определить количество вершин в луче, построенном над ними.

Входные данные:
В первой строчке находится число N - количество слов, N не превышает 10000
В каждой следующий строчке записано очередное слово, состоящее из заглавных английских букв.
Длина слова не превышает 20 символов.

Выходные данные:
Одно число - количество вершин в луче

Пример входных данных:
4
CAT
CLEAR
CAR
MORE

Пример выходных данных:
13
Пояснение примера. На рисунке изображен луч, построенный над набором слов 'CAT', 'CLEAR', 'CAR', 'MORE'.

имеющийся код:

#include <string>
#include <iostream>
 
using namespace std;
 
struct node {                   // объявление структуры для дерева
    node *children[25];
};
 
int _tmain(int argc, _TCHAR* argv[]) {
    node *tree = new struct node;  // выделение памяти для дерева
    for (int i = 0; i < 25; ++i)             // обнуления веток
        tree->children[i] = NULL;
 
    node *current = tree;// присвоение текущей вершини - первой
 
    int N, cnt = 1;
    cin >> N; // считываем количество слов
    for (int i = 0; i < N; ++i) {
        string word;
        cin >> word; // считывание слова
        current = tree;
        for (int j = 0; j < word.length(); ++j) { // цикл по количеству символов в слове
            if (current->children[word[j] - 65] == NULL) {         //если элемент  под номером (код символа - 65) = NULL тогда
                current->children[word[j] - 65] = new struct node;// создаем новую ветку, выделяем память.
                current = current->children[word[j] - 65];  //переносим указатель текущей ветки на только, что "созданной ветке"
                cnt++;// увеличиваем счетчик вершин
                for (int m = 0; m < 25; ++m) {  //обнуления подветок только что созданной ветки
                    current->children[m] = NULL;
                }
            }
            else {        //если элемент под номером (код символа - 65)  не NULL тогда
                current = current->children[word[j] - 65];// переходим к следующей подветке
            }
        }
    }
    cout << cnt << endl;// вывод результата
    return 0;
}

[Poma][a]

Залейте фотку через расширенный режим-управление вложениями
И было бы прекрасно, если бы Вы дали ссылку на задачу

[Dmitry_DM]

http://atpp.vstu.edu.ru/cgi-bin/arh_....pl?id_prb=253

[Poma][a]

Ставлю на то, что все проблемы из-за того, что Вы не освобождаете память

[Dmitry_DM]

Сообщение от Poma][a

Ставлю на то, что все проблемы из-за того, что Вы не освобождаете память

возможно, а если так, то как высвободить память в моем случае?

[Dmitry_DM]

вот ссылка на алгоритм, который подошел бы... но он не компилирует, выдавая ошибки:
'cend' is not a member of 'LinksMap'
'cbegin' is not a member of 'LinksMap'
'cend' is not a member of 'LinksMap'
что делать?

[Poma][a]

вот ссылка на алгоритм, который подошел бы...

Не, не подошел бы

возможно, а если так, то как высвободить память в моем случае?

Пробежаться по всем детям рекурсием..
Что-то типа :

void delete_tree (node *current)
{
    if (current == NULL) return;
    for (int i = 0; i < 25; ++i)  
                    delete(current->children[m]);
    <а тут удаляем.. не помню как>
}

[Dmitry_DM]

а если все-таки вспомнить, как удалить?
напишите, пожалуйста!

[Poma][a]

delete current

[Dmitry_DM]

ну и не помогло это... как был лимит памяти, так и остался

#include <string>
#include <iostream>
 
using namespace std;
 
struct node {                   // объявление структуры для дерева
    node *children[25];
};
 
 void delete_tree (node *current)
{
    if (current == NULL) return;
    for (int i = 0; i < 25; ++i)  
                    delete(current->children[i]);
    delete current;
}
 
 
int main() {
    node *tree = new struct node;  // выделение памяти для дерева
    for (int i = 0; i < 25; ++i)             // обнуления веток
        tree->children[i] = NULL;
 
    node *current = tree;// присвоение текущей вершини - первой
 
    int N, cnt = 1;
    cin >> N; // считываем количество слов
    for (int i = 0; i < N; ++i) {
        string word;
        cin >> word; // считывание слова
        current = tree;
        for (int j = 0; j < word.length(); ++j) { // цикл по количеству символов в слове
            if (current->children[word[j] - 65] == NULL) {         //если элемент  под номером (код символа - 65) = NULL тогда
                current->children[word[j] - 65] = new struct node;// создаем новую ветку, выделяем память.
                current = current->children[word[j] - 65];  //переносим указатель текущей ветки на только, что "созданной ветке"
                cnt++;// увеличиваем счетчик вершин
                for (int m = 0; m < 25; ++m) {  //обнуления подветок только что созданной ветки
                    current->children[m] = NULL;
                }
            }
            else {        //если элемент под номером (код символа - 65)  не NULL тогда
                current = current->children[word[j] - 65];// переходим к следующей подветке
            }
        }
    }
    delete_tree(tree);
    cout << cnt << endl;// вывод результата
    return 0;
}