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

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

В некоторой социальной сети зарегистрированы 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("");
}