Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
1

Предки в графах

26.03.2018, 12:55. Просмотров 912. Ответов 12

Задача на определение, является ли вершина предком другой

Условие:
Кликните здесь для просмотра всего текста
Определить для двух вершин дерева , является ли одна из них предком другой.

Входные данные

Первая строка - количество вершин в дереве n (1 ≤ n ≤ 100000). Вторая строка - n чисел, i-ое из которых определяет номер непосредственного родителя вершины с номером i. Если это число равно нулю, то вершина является корнем дерева.

В третьей строке находится количество запросов m (1 ≤ m ≤ 100000). Каждая из следующих m строк содержит два различных числа a и b (1 ≤ a, b ≤ n).

Выходные данные

Для каждого из m запросов вывести в отдельной строке число 1, если вершина a является одним из предков вершины 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


Прошёл дфсом, запоминая время входа и выхода из вершин. Затем сравнивал: если (time_in[x]<time_in[y]) и (time_out[x]>=time_out[y]), то x - предок y.

Пишет: "ошибка выполнения". В чём может быть проблема? Размер массива или, может, метод не подходит?


Код:
Кликните здесь для просмотра всего текста
Pascal
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
var
t1, t2: array[1..100000] of integer;
visited: array[1..100000] of boolean;
a: array[1..100000, 1..100000] of byte;
i, j, n, m, kol, x, y : longint;
procedure dfs(v: longint);
var i: longint;
begin
  inc(kol);
  t1[v] := kol;
  visited[v] := true;
  
  for i := 1 to n do
    if (not visited[i]) and (a[v, i] = 1) then dfs(i);
  t2[v] := kol;
end;
 
begin
readln(n);
for i := 1 to n do
begin
  read(x);
  if x <> 0 then
  a[x, i] := 1;
end;
dfs(1);
readln(m);
for i := 1 to m do
begin
  readln(x, y);
  if (t1[x]<t1[y]) and (t2[x]>=t2[y]) then writeln('1') else writeln('0');
end;
end.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2018, 12:55
Ответы с готовыми решениями:

ГА на графах
Здравствуйте. Не могу разобраться как решать эту задачу. Используйте...

Алгоритмы на графах
Поиск минимального остовного дерева как-то связан с поиском кратчайших путей...

Алгоритм А* на графах
Стоит задача разработать функцию поиска пути в неориентированном графе методом...

Алгоритмы на графах
Привет всем, мне нужна помощь з алгоритмами на графах нашел алгоритм Дейсктры...

Список смежности во взвешенных графах
Здрасте! Не получается реализовать списки смежности для ВЗВЕШЕННОГО графа. ...

12
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
26.03.2018, 15:01 2
Цитата Сообщение от Chvick Посмотреть сообщение
Пишет: "ошибка выполнения"
И всё?
0
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
26.03.2018, 15:03  [ТС] 3
Shamil1, да. Но когда уменьшаю размер массива - эта ошибка только в половине тестов, а во второй - "неправильный ответ"
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
26.03.2018, 15:05 4
Цитата Сообщение от Chvick Посмотреть сообщение
метод не подходит
Реализация не подходит?

Добавлено через 31 секунду
Цитата Сообщение от Chvick Посмотреть сообщение
да.
А Вы не пробовали у себя код запускать?
0
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
26.03.2018, 15:07  [ТС] 5
Shamil1, пробовал. Всё работает, ответ верный
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
26.03.2018, 15:07 6
1. Не используйте матрицу смежности.
2. Протестируйте отдельно функцию dfs.
1
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
26.03.2018, 15:09  [ТС] 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Реализация не подходит?
, да. Вдруг, это решается не графами

Добавлено через 38 секунд
Цитата Сообщение от Shamil1 Посмотреть сообщение
Не используйте матрицу смежности.
Как?
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
26.03.2018, 15:12 8
Цитата Сообщение от Chvick Посмотреть сообщение
пробовал. Всё работает, ответ верный
На максимальном размере пробовали?

Добавлено через 36 секунд
Цитата Сообщение от Chvick Посмотреть сообщение
Как?
Для каждой вершины храните список детей.

Добавлено через 2 минуты
Цитата Сообщение от Shamil1 Посмотреть сообщение
На максимальном размере пробовали?
Не забудьте случай, когда граф представляет из себя цепочку.
0
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
26.03.2018, 15:14  [ТС] 9
Цитата Сообщение от Shamil1 Посмотреть сообщение
На максимальном размере пробовали?
Нет, сейчас попробую

Добавлено через 1 минуту
Цитата Сообщение от Shamil1 Посмотреть сообщение
Не забудьте случай, когда граф представляет из себя цепочку.
Это дерево
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
26.03.2018, 15:27 10
Цитата Сообщение от Chvick Посмотреть сообщение
Это дерево
Цепочка является деревом. Глубина дерева равна количеству элементов.
1
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
26.03.2018, 16:24  [ТС] 11
Shamil1, с цепочкой работает, но на больших входных данных пишет, что программа завершена из-за переполнения программного стека
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,412
26.03.2018, 22:14 12
Лучший ответ Сообщение было отмечено Chvick как решение

Решение

Цитата Сообщение от Chvick Посмотреть сообщение
программа завершена из-за переполнения программного стека
Замените рекурсию циклом.

з.ы. И почему Вы не используете нормальные структуры данных вместо массивов?
1
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
26.03.2018, 22:38  [ТС] 13
Цитата Сообщение от Shamil1 Посмотреть сообщение
почему Вы не используете нормальные структуры данных вместо массивов?
Shamil1, потому что только вчера начал изучать графы)

Добавлено через 5 минут
Думаю, именно использование матрицы смежности является проблемой. Бегу исправлять
0
26.03.2018, 22:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.03.2018, 22:38

Порядок сборки программного комплекса на графах
Ребят, помогите пожалуйста понять смысл курсовой по &quot;алгоритмам и структурам...

Двунаправленный поиск кратчайшего пути в графах
Никто не встречал реализованный на c\c++ алгоритм? Добавлено через 17 часов...

Алгоритмы на графах, формирование двудольного неориентированного графа
Пишу на c#, у нас есть множество вершин графа, хранящихся в List&lt;V&gt; Множество...


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

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

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