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

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

26.03.2018, 12:55. Просмотров 1324. Ответов 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)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2018, 12:55
Ответы с готовыми решениями:

Родословная: предки и потомки
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. ...

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

ООП+матрицы(предки потомки)свойства и т.п. нужна помошь
Всем привет. Вот собственно задача: Описать тип-объект MATRIX (матрица произвольной размерности...

Кто построил чудеса света: наши предки или инопланетяне?
Вот смотрю я на этих всех телепередачи уфологов и прочих загадочных &quot;ученых&quot; и тихо умиляюсь... Как...

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

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

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

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

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

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

Решение

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

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

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

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

Операции на графах
бывает ли графы с 11 вершинами, степени которых 1,1,1,2,2,2,3,4,4,5,5? Если есть, то, что для...

Задача о графах
Помогите решить или объясните как написать код к данной программе. Имеется N точек и M...

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


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

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

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