Вроде бы простая алгоритмическая задача

[MAnt]

В социальной сети зарегистрировано $n$ человек. Каждый участник может подписываться на сообщения других участников, причем если человек $A$ подписан на $B$, то из этого не следует, что $B$ подписан на $A$. Известно, что среди зарегистрированных пользователей есть знаменитость - человек, на которого подписаны все $n-1$ других пользователей, но сам он не подписан ни на кого. При помощи одного запроса к серверу вы можете определить, подписан ли человек $A$ на сообщения человека $B$. Предложите алгоритм, позволяющий найти знаменитость за не более чем $n$ запросов к серверу.

Что такое почитать, чтобы решать такую и подобные задачи?

[venco]

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

[Pavia]

MAnt
Задачка простая на внимательность и умение логически мыслить.

[MAnt]

venco
если $A$ подписан на $B$, то $A$ не знаменитость.
если $A$ не подписан на $B$, то $B$ не знаменитость.
Понятно, вычеркиваем одного человека. За $n$ запросов вычеркнем $n$ человек. Спасибо

А какие есть доступные книги по графам?

[Teletranslator]

Доступное - это что-то вроде "Введения в дискретную математику".

[Pavia]

MAnt
Вы решили неправильно. Ещё раз внимательно посмотрите на условие задачи. И посмотрите на то что вы написали. Каким условием вы не воспользовались из условия?

Что касается графов то "Программирование в алгоритмах" Автор: С. Окулов

[venco]

А мне кажется, что решение правильное.

[Pavia]

venco
Да точно. Неправильно прочитал. Бывает.

[Tookser]

Можно ещё Райгородского почитать, хотя там больше комбинаторики. Книга называется "Комбинаторика и теория вероятности", но таких у него может быть больше одной. Та, про которую я говорю, тонкая (страниц 100), и в ней графам отведено примерно 20 страниц.

[arseniiv]

(Оффтоп)

MAnt в сообщении #885097 писал(а):

При помощи одного запроса к серверу вы можете определить, подписан ли человек $A$ на сообщения человека $B$.

Главное, чтобы в реальной системе такого не было — и серверу обычно проще (имею в виду, меньше оверхеда) выдать, например, всех, на кого подписался $A$, а не только одну проверку, и передаваться маленькие повторные запросы-ответы, наверно, немного дольше будут, ну и в самом клиенте тоже может быть чуть проще.

К задаче это, конечно, никаким боком — хотя у неё могла бы быть и другая формулировка, не вызывающая такие ассоциации.