Решение задачи Распространение новостей с Codeforces
С пояснением   Просмотров: 104
Изначально какой-нибудь пользователь x узнает новость из какого-то внешнего источника. Затем этот пользователь отправляет новость всем своим друзьям (два пользователя считаются друзьями, если они оба принадлежат к какой-нибудь группе). Друзья продолжают отправлять новость своим друзьям, и так далее. Процесс заканчивается, когда не останется ни одной пары друзей, в которой один пользователь знает новость, а другой — нет.
Для каждого пользователя x определите, сколько пользователей в конечном итоге узнает новость, если x начнет ее распространять.
Пояснение к задаче
Первое желание, которое возникает после прочтения задачи, — это перефразировать ее в терминах теории графов. Пусть люди будут вершинами, вершины x и y соединены ребром, если у x и y есть какая-нибудь общая группа. На самом деле, если x начинает распространять новость, то все в его компоненте связности ее получают. Тогда задача — это посчитать количество вершин в компоненте каждой вершины.
Сейчас в графе может быть до O(n2) ребер (взгляните на тест, где все находятся в одной группе). Уменьшим количество ребер, не изменяя компоненты связности. Для каждой группы точно известно, что люди в ней находятся в одной компоненте. Соединим тогда не вообще все пары вершин, а только пары соседних в группе. Легко заметить, что все останутся в тех же компонентах.
В этом графе уже O(∑i=1mk[i]) ребер, что является гораздо меньшим числом. Можно использовать поиск в глубину или СНМ для нахождения компонент связности и их размеров.
Асимптотика решения: O(n+∑i=1mk[i]).