Как построить граф или проверить связь?

@Mox0n · Регистрация: 31.05.2019

Студворк — интернет-сервис помощи студентам

В первой строке вводится дерево в виде списка предков,т.е. i-ый элемент списка содержит порядковый номер для i-ой вершины.
Во второй строке вводится номер вершины.
Нужно проверить, соединены ли вершины 0-ая и i-ая. Иными словами,проверить является ли введенная вершина предком корневой вершины.
Ввод:
0 0 1 2 3 1 2 3(0 вершина-корневая,1-ая вершина соединена с 0,2-ая вершина с 1 и т.д.)
6
Вывод:
True
Я создал словарь,где ключи-вершины,а значения - связь между вершинами,но я не знаю как мне теперь определить связь 0-вой и i-ой вершины.Буду рад любой помощи.

Python

k=list(map(int,input().split()))
b={}
for i in range(len(k)):
  b[i]=k[i]

@Fortran Cobolov · 23.06.2019, 19:13

Сообщение от Mox0n

Иными словами,проверить является ли введенная вершина предком корневой вершины.

У корневой вершины не может быть предка (наверно, речь шла о потомке). Если дерево связное, то любая вершина является потомком корневой.
Нужно как-то точнее формулировать задачу

@Fortran Cobolov 11 / 9 / 11 Регистрация: 14.06.2017 Сообщений: 20
	23.06.2019, 19:13	2
	Сообщение от Mox0n Иными словами,проверить является ли введенная вершина предком корневой вершины. У корневой вершины не может быть предка (наверно, речь шла о потомке). Если дерево связное, то любая вершина является потомком корневой. Нужно как-то точнее формулировать задачу 0

Опции темы