Задча на граф Опции

[r-d-v2008]

Люди помогите пожалуйста решить задачу: Проверьте, содержит ли граф, заданный с помощью списков инцидентности, вершину, в которую входят дуги от всех остальных вершин графа, но из которой не исходит ни одна дуга.

[volvo]

Что такое список инцидентности - знаешь? Реализация этого списка есть у тебя? Где, собственно, граф, который надо проверить?

Если знаешь, что такое списки инцидентности - то задачу решишь без труда. Достаточно просто пройти по массиву указателей, и проверить, есть ли там указатели, равные Nil... Если таких нет - то из каждой вершины что-то да выходит, ответ на твой вопрос - "Нет". Если nil есть (причем ровно 1 - больше тоже быть не должно, подумай, почему) - то ходить по всем указателям, не равным Nil, как по спискам, и проверять, есть ли в каждом из списков вершина с индексом, равным индексу того самого злополучного Nil-а. Если везде, во всех просмотренных списках есть такая вершина - значит, ответ "Да", иначе - опять "Нет". На этот раз ответ окончательный, больше ничего проверять не надо...

Все просто, как видишь. Осталось всего лишь этот алгоритм запрограммировать...