Neka je data društvena mreža u kojoj ljudi mogu da se međusobno povezuju. Kada se 2 osobe A i B iz 2 različite mreže povezuju potrebno je spojiti mreže kojima pripadaju A i B u jednu mrežu. Na početku postoji \(n\) osoba i \(n\) mreža.
Postoje 2 tipa upita:
1. M a b - osobe a i b se povezuju 2. Q a - odrediti veličinu društvene mreže kojoj pripada osoba a
Sa standardnog ulaza se unose vrednosti \(a\) i \(q\) koje predstavljaju broj ljudi i broj upita redom. U narednih \(q\) linija se unose upiti.
Na standardni izlaz za svaki Q upit ispisati veličinu društvene mreže kojoj pripada osoba A.
3 6 Q 1 M 1 2 Q 2 M 2 3 Q 3 Q 2
1 2 3 3
U ovom bloku se opisuje glavno rešenje zadatka.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> roditelj;
vector<int> rang;
vector<int> broj;
void napravi_dsu(int n) {
roditelj.resize(n);
rang.resize(n, 1);
broj.resize(n);
for(int i = 0; i < n; i++) {
roditelj[i] = i;
broj[i] = 1;
}
}
int predstavnik(int a) {
while(roditelj[a] != a)
a = roditelj[a];
return a;
}
void unija(int a, int b) {
a = predstavnik(a);
b = predstavnik(b);
if(a == b)
return;
if(rang[a] < rang[b]) {
roditelj[a] = b;
rang[b] += rang[a];
broj[b] = broj[a] + broj[b];
}
else {
roditelj[b] = a;
rang[a] += rang[b];
broj[a] = broj[a] + broj[b];
}
}
int main() {
int n, q, a, b;
cin >> n >> q;
napravi_dsu(n);
while(q--) {
string upit;
cin >> upit;
if(upit == "M") {
cin >> a >> b;
unija(a, b);
}
else if(upit == "Q") {
cin >> a;
cout << broj[predstavnik(a)] << '\n';
}
}
return 0;
}