Решение задачи 501
В графе 100 вершин, какие-то соединены ребрами, но мы не знаем какие. Мы можем выбрать любую пару вершин и получить ответ на вопрос “есть ли ребро между ними?”. Какое наименьшее число вопросов надо задать, чтобы гарантированно выяснить является ли граф связным?
Нужно задать 4950 вопросов, то есть спросить про все ребра. Теперь мы будем на стороне отвечающего и покажем, как надо отвечать на вопросы, чтобы до последнего ребра был неясен ответ.
Изначально в графе все ребра серые. Если мы решаем, что соответствующее серое ребро есть, то красим его в зеленый цвет, иначе в красный. Максимальное по включению связное множество зеленых ребер будем называть компонентой связностью (одинокая вершина тоже является компонентой связности).
Пусть игрок спрашивает про какое-то серое ребро. Оно соединяет две компоненты связности (дальше будет ясно почему). Если между этими двумя компонентами нет других серых ребер, то красим интересующее игрока серое ребро в зеленый цвет. Иначе красим его в красный.
Почему серые ребра в любой момент соединяют компоненты связности? Изначально это верно. Пусть это верно в какой-то момент. Если ребро стало красным, то конфигурация компонент не поменялась. Если ребро стало зеленым, то две компоненты соединились в одну, и все ребра между этими компонентами красные, кроме новой зеленой.
Также нетрудно видеть, что компонента связности не может стать "изолированной", то есть из нее вне не могут выходить только красные ребра, так как последнее оставшееся серое ребро точно станет зеленым.
Значит, перед последним ходом игрока останется одно серое ребро, соединяющее две компоненты связности. Про это ребро игрок тоже обязан задать вопрос, чтобы выяснить связен ли граф или нет.