Решение задачи Распространение новостей с Codeforces

С пояснением   Просмотров: 104

В некоторой социальной сети зарегистрированы n пользователей. Они общаются между собой в m группах. Давайте рассмотрим процесс распространения новостей между пользователями.

Изначально какой-нибудь пользователь x узнает новость из какого-то внешнего источника. Затем этот пользователь отправляет новость всем своим друзьям (два пользователя считаются друзьями, если они оба принадлежат к какой-нибудь группе). Друзья продолжают отправлять новость своим друзьям, и так далее. Процесс заканчивается, когда не останется ни одной пары друзей, в которой один пользователь знает новость, а другой — нет.

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

Код 

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 500 * 1000 + 13;

int n, m;
int rk[N], p[N];

int getP(int a){
	return (a == p[a] ? a : p[a] = getP(p[a]));
}

void unite(int a, int b){
	a = getP(a), b = getP(b);
	if (a == b) return;
	if (rk[a] < rk[b]) swap(a, b);
	p[b] = a;
	rk[a] += rk[b];
}

int main(){
	scanf("%d%d", &n, &m);
	forn(i, n) p[i] = i, rk[i] = 1;
	
	forn(i, m){
		int k;
		scanf("%d", &k);
		int lst = -1;
		forn(j, k){
			int x;
			scanf("%d", &x);
			--x;
			if (lst != -1)
				unite(x, lst);
			lst = x;
		}
	}
	
	forn(i, n)
		printf("%d ", rk[getP(i)]);
	puts("");
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Первое желание, которое возникает после прочтения задачи, — это перефразировать ее в терминах теории графов. Пусть люди будут вершинами, вершины x и y соединены ребром, если у x и y есть какая-нибудь общая группа. На самом деле, если x начинает распространять новость, то все в его компоненте связности ее получают. Тогда задача — это посчитать количество вершин в компоненте каждой вершины.

Сейчас в графе может быть до O(n2) ребер (взгляните на тест, где все находятся в одной группе). Уменьшим количество ребер, не изменяя компоненты связности. Для каждой группы точно известно, что люди в ней находятся в одной компоненте. Соединим тогда не вообще все пары вершин, а только пары соседних в группе. Легко заметить, что все останутся в тех же компонентах.

В этом графе уже O(∑i=1mk[i]) ребер, что является гораздо меньшим числом. Можно использовать поиск в глубину или СНМ для нахождения компонент связности и их размеров.

Асимптотика решения: O(n+∑i=1mk[i]).



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта