Дана эпидемия, в результате которой весь город заражен компьютерным вирусом. Власти ввели масочный режим, а в кинотеатр "Малина" теперь можно попасть только по электронному сертификату о прививке. Для того чтобы попасть в кинотеатр, каждый зритель должен предъявить свой сертификат. Требуется найти количество способов выбрать некоторое подмножество из всех возможных сертификатов, такое что оно образует связный граф (т.е. между любыми двумя сертификатами существует путь). Задача может быть решена с использованием динамического программирования. Пусть n - количество людей, целое число от 1 до 1000, a[i] - номер персоны, у которой есть сертификат прививки. x[i] - номер персоны, прививка которой строго раньше. По условию a[i] < x[i] для каждой пары (i, j). Тогда для каждого человека a[i] найдем все номера j, для которых a[j] = x[i]. Полученные значения занесем в структуру данных типа вектор или список. Затем следует инициализировать динамический массив dp[n+1], где n - количество людей, dp[i] - количество способов выбрать связное подмножество из людей с номерами от 1 до i. Далее следует пройтись по каждому человеку в порядке возрастания номеров. Если человек i не имеет правильного сертификата, то dp[i] = dp[i-1]. В противном случае, dp[i] равно сумме всех dp[j], где j - номер человека с сертификатом прививки x[i]. Искомое количество способов будет равно dp[n]. Рассмотрим пример. Пусть даны следующие сертификаты: 4, 3, 2, 1. Для сертификата 1 есть два возможных варианта - выбрать только его (т.е. комбинация {1} есть связное множество), или выбрать его и второй сертификат (комбинация {1, 2} также связное множество). Для сертификата 2 есть 3 варианта - выбрать только его ({2}), выбрать его и первый сертификат ({1, 2}), или выбрать его и третий сертификат ({2, 3}). И т.д. Итого, количество комбинаций будет равно 1 + 2 + 3 + 4 = 10. Сложность алгоритма - O(n^2), где n - количество людей. Таким образом, задача может быть решена за разумное время даже при больших значениях n.