Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
CAXOPOK
1 / 1 / 0
Регистрация: 29.03.2013
Сообщений: 59
1

Ускорить обход дерева

25.01.2015, 21:02. Просмотров 398. Ответов 6
Метки нет (Все метки)

Во входном файле ancestor.in в первой строке содержится количество узлов дерева, во второй строке массив чисел i-ое из которых определяет родителя вершины с номером i (0 - корень). В третьей строке число m - количество запросов, далее в m строках числа а и b(1<=a, b<=n).
Для каждого запроса в отдельную строку записать 1, если а является одним из предков b, иначе записать в строку 0.
пример входных данных
6
0 1 1 2 3 3
5
4 1
1 4
3 6
2 6
6 5
ответ
0
1
1
0
0
Вот что набросал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<fstream>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;
struct node
{
    int parent;
    set<int> children;
};
bool searcher(node* array, int a, int b)
{
    if( array[a].children.count(b)==1)
        return true;
    if(array[b].parent==0)
        return false;
            if(array[b].parent==a)
    {
     array[a].children.insert(b); 
     return true;
    }
    return searcher(array, a, array[b].parent);
}
 
int main()
{
    FILE *f;
    
    f=fopen("ancestor.in","r");
    int length;
    fscanf(f,"%d",&length);
    int tmp;
    node* array = new node[length+1];
    for(int i = 1; i <= length; ++i)
    {
        fscanf(f,"%d",&tmp);
        array[i].parent=tmp;    
        array[tmp].children.insert(i);
}   
    int numberOfRequests;
    fscanf(f,"%d",&numberOfRequests);
    int a,b;
 
    FILE *f2=fopen("ancestor.out","w");
    while(--numberOfRequests >= 0)
    {
        fscanf(f,"%d",&a);
        fscanf(f,"%d",&b);  
        if(searcher(array,a,b))
        {
            fprintf(f2,"1\n");
        }
        else
     fprintf(f2,"0\n");
 }  
    return 0;
}
Работает правильно, но медленно. Ошибка "Превышено отведённое время" (тест далеко не первый).
Пробовал ставить условие b>=a для ограничения перебора, но ошибки сразу в начальных тестах. Потому вопрос, как этот алгоритм можно ускорить?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.01.2015, 21:02
Ответы с готовыми решениями:

Обход дерева
Почему обход дерева идёт с левой стороны направо?

Обратный обход дерева за 0(n)
Кто может подсказать алгоритм за 0(n) вывода последовательности ключей бинарного дерева в порядке...

Печать на консоль бинарного дерева, обход в ширину
Добрый вечер! Сразу скажу, топик не для слабонерных. Выручайте уважаемые программисты. Встала...

Подскажите пример, где требуется обход дерева в обратном порядке
Пишу учебный текст про обходы бинарных деревьев. Как известно есть три способа: прямой, обратный и...

Ускорить обход дерева
Во входном файле ancestor.in в первой строке содержится количество узлов дерева, во второй строке...

6
salam
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
25.01.2015, 21:41 2
надо придумать другой алгоритм, который будет отвечать на запросы за http://www.cyberforum.ru/cgi-bin/latex.cgi?\mathcal{O(1)}.
0
CAXOPOK
1 / 1 / 0
Регистрация: 29.03.2013
Сообщений: 59
25.01.2015, 21:45  [ТС] 3
Отвечает за О(1), но снова не проходит по времени на том же тесте
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            System.IO.StreamReader file = new System.IO.StreamReader(@"ancestor.in");
            int Length = int.Parse(file.ReadLine());
            string[] arr = file.ReadLine().Split(' ');
            int[] array = new int[Length + 1];
            array[0] = -1;
 
            for (int i = 1; i <= Length;++i )
            {
                array[i] = int.Parse(arr[i - 1]);
            }
            List<int>[] Table = new List<int>[Length+1];
            for (int i=0; i<=Length;++i)
            {
              Table[i] = new List<int>();
            }
            
            int parent;
            for(int i = 1; i <=Length;++i)
            {
                parent = array[i];
                while(parent>0)
                {
                    Table[parent].Add(i);
                    parent = array[parent];
                }
            }
            int RequestNumber=int.Parse(file.ReadLine());
            int a, b;
            System.IO.StreamWriter sw = new System.IO.StreamWriter("ancestor.out");
            while(RequestNumber-->0)
            {
                arr = file.ReadLine().Split(' ');
                a = int.Parse(arr[0]);
                b = int.Parse(arr[1]);
                if(Table[a].Contains(b))
                {
                    sw.WriteLine("1");
                }
                else
                {
                    sw.WriteLine("0");
                }
            }
            sw.Close();
 
        }
    }
}
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
25.01.2015, 23:41 4
CAXOPOK, код, который заполняет массив table, работает за O(n^2). да и метод контейнс работает походу за O(n). И памяти массив table тоже жрет квадрат.
0
CAXOPOK
1 / 1 / 0
Регистрация: 29.03.2013
Сообщений: 59
26.01.2015, 10:30  [ТС] 5
Памяти он занимает О(n*n) только в худшем случае, когда не дерево, а линия прямая. А contains за O(log n) работает
0
SlavaSSU
218 / 163 / 47
Регистрация: 17.07.2012
Сообщений: 587
26.01.2015, 10:54 6
CAXOPOK, ну. квадрат времени и квадрат памяти.
0
CAXOPOK
1 / 1 / 0
Регистрация: 29.03.2013
Сообщений: 59
26.01.2015, 20:18  [ТС] 7
Переделал под С++, время ответа на запрос О(1), но пошли ошибки исполнения.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<fstream>
#include<vector>
#include<iostream>
 
 
using namespace std;
class node
{
    public :
        vector<node*> children;
    int nasledniki;
        node()
    {
        nasledniki=0;
    }
    int number;
    int Numerate( int& num)
        {
            number = num;
            num++;
            nasledniki = children.size();
            if (children.size() > 0)
            {
                for(int i = 0; i < children.size();++i)
                {
                   nasledniki += children[i]->Numerate(num);
                } 
                
            }
            return nasledniki;
 
        }
};
 
int main()
{
 FILE *f;
   
    f=fopen("ancestor.in","r");
    int length;
    fscanf(f,"%d",&length);
    int tmp;
    node** nodeArr = new node*[length+1];
    int* array = new int(length+1);
    array[0]=0;
    nodeArr[0]=new node;
    for(int i = 1; i<=length;i++)
    {
        nodeArr[i]=new node;
        fscanf(f,"%d",&tmp);
        array[i]=tmp;
    }
    for(int i =1;i<=length;++i)
    {
        nodeArr[ array[i] ]->children.push_back(nodeArr[i]);
    }
    tmp=1;
    for(int i = 1; i<=length;i++)
    {
        if(array[i]==0)
        {
            
            nodeArr[i]->Numerate(tmp);
            break;
        }
    }
    
 
//  for(int i =1;i<=length;i++)
//  {
//      cout<<nodeArr[i]->number<< " ";
//  }
    int numberOfRequests;
    fscanf(f,"%d",&numberOfRequests);
    int a,b;
    FILE *f2=fopen("ancestor.out","w");
    while(--numberOfRequests >= 0)
    {
        fscanf(f,"%d",&a);
        
        fscanf(f,"%d",&b);  
        
        if(b>nodeArr[a]->number&&b<=nodeArr[a]->number+nodeArr[a]->nasledniki)
        {
            fprintf(f2,"1\n");
        }
        else
     fprintf(f2,"0\n");
    }  
    fclose(f2);
    fclose(f);
    return 0;
}
Добавлено через 37 минут
Есть этот же код и на шарпе

Добавлено через 4 часа 6 минут
Поясню, в памяти создаётся дерево (не бинарное) далее делаю его рекурсивный обход (корень, потомки по списку), и нумерую все узлы и запоминаю общее число потомков (не обязательно прямых). Это даёт возможность проверить родство узлов за время O(1). В массиве беру адрес нужны узлов и сравниваю. Значение в узле b должно быть больше значения в а но меньше либо равно значению в а + количество потомков а. На примере работает, но при тестировании системой выдаёт ошибку выполнения сразу на втором тесте.

Добавлено через 3 часа 28 минут
Подправил, но есть ошибки исполнения на уже других тестах
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<fstream>
 
#include<vector>
#include<iostream>
 
 
using namespace std;
class node
{
    public :vector<node*> children;
    int nasledniki;
    node()
    {
        nasledniki=0;  
    }
    int number;
    int Numerate( int& num)
        {
            number = num;
            num++;
            nasledniki = children.size();
            if (children.size() > 0)
            {
                for(int i = 0; i < children.size();++i)
                {
                   nasledniki += children[i]->Numerate(num);
                } 
                
            }
            return nasledniki;
 
        }
};
 
int main()
{
 FILE *f;
   
    f=fopen("ancestor.in","r");
    int length;
    fscanf(f,"%d",&length);
    int tmp;
    node** nodeArr = new node*[length+1];
    int* array = new int(length+1);
    array[0]=0;
    nodeArr[0]=new node;
    for(int i = 1; i<=length;i++)
    {
        nodeArr[i]=new node;
        fscanf(f,"%d",&tmp);
        array[i]=tmp;
    }
    for(int i =1;i<=length;++i)
    {
        nodeArr[ array[i] ]->children.push_back(nodeArr[i]);
    }
    tmp=1;
    for(int i = 1; i<=length;i++)
    {
        if(array[i]==0)
        { 
            nodeArr[i]->Numerate(tmp);
        }
    }
 
    int numberOfRequests;
    fscanf(f,"%d",&numberOfRequests);
    int a,b;
    FILE *f2=fopen("ancestor.out","w");
    while(--numberOfRequests >= 0)
    {
        fscanf(f,"%d",&a);
        fscanf(f,"%d",&b);
          
        if(a>length || b>length || a<1||b<1)
        {
            fprintf(f2,"0\n");
            continue;
        }
        if( nodeArr[b]->number>nodeArr[a]->number  &&  nodeArr[b]->number<=nodeArr[a]->number+nodeArr[a]->nasledniki)
        {
            fprintf(f2,"1\n");
        }
        else
        fprintf(f2,"0\n");
    }  
    fclose(f2);
    fclose(f);
    return 0;
}
0
26.01.2015, 20:18
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2015, 20:18

Операции над бинарными деревьями: построение дерева, обход дерева, вставка и удаление элемента дерева
Пожалуйста кто сможет, помогите составить программу: Организация по трудоустройству населения...

Построение бинарного дерева. Обход дерева
Построить дерево поиска с элементами – числами. С использованием операций Locate и DeleteLeft найти...

Обход дерева
Узел дерева имеет поля: char letter; // символ int frequency; //частота вхождения в текст этого...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.