Na velikom arhipelagu ima \(n\) ostrva označenih brojevima \(1,2,\ldots,n\). U početku nema mostova i svako ostrvo je samostalno. Tokom vremena događaju se operacije:
Vaš zadatak je da obradite niz operacija i da za svaku informativnu operaciju ispišete odgovor.
Sa standardnog ulaza se unosi broj ostrva \(n\) (\(1 \leq n \leq 10^5\)) i broj upita \(m\) (\(1 \leq m \leq 10^5\)).
U sledećih \(m\) redova, unosi se po jedna operacija oblika:
U a b — uspostavi most između ostrva a i
b. Nakon toga, ostrva a i b se
nalaze u istoj grupi ostrva.P a b — proveri da li su a i
b trenutno u istoj grupi. Ispiši DA ili
NE.V a — ispiši veličinu grupe kojoj pripada ostrvo
a.K — ispiši koliko grupa ostrva trenutno postoji.Za svaku operaciju tipa P, V ili
K ispišite po jedan red sa traženim odgovorom.
7 11 K U 1 2 U 2 3 V 2 P 1 4 U 4 5 U 6 7 K U 3 4 P 5 1 V 6
7 3 NE 3 DA 2
Na početku ima 7 odvojenih ostvra \(\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}\).
K ispisuje broj grupa: 7.U 1 2 spaja ostrva 1 i 2: \(\{1, 2\}, \{3\}, \{4\}, \{5\}, \{6\},
\{7\}\).U 2 3 spaja ostrva 2 i 3: \(\{1, 2, 3\}, \{4\}, \{5\}, \{6\},
\{7\}\).V 2 ispisuje broj ostva u grupi gde se nalazi 2:
3.P 1 4 proverava da li se ostrvo 1 i ostrvo 4 nalaze u
istoj grupi: NE.U 4 5 spaja ostrva 4 i 5: \(\{1, 2, 3\}, \{4, 5\}, \{6\}, \{7\}\).U 6 7 spaja ostrva 6 i 7: \(\{1, 2, 3\}, \{4, 5\}, \{6, 7\}\).K ispisuje broj grupa: 3U 3 4 spaja ostrva 3 i 4: \(\{1, 2, 3, 4, 5\}, \{6, 7\}\).P 5 1 proverava da li se ostrvo 5 i ostrvo 1 nalaze u
istoj grupi: DA.V 6 ispisuje broj ostva u grupi gde se nalazi 6:
2.Rešenje koristi implementaciju strukture disjunktnih skupova
(Union-Find) sa optimizacijama: kompresija puta i spajanje po veličini.
Spajanje po veličini je varijanta spajanja gde se manji skup spaja u
veći. Spajanje po veličini omogućava efikasno implementiranje operacije
V a, jer se veličina grupe može lako održavati prilikom
spajanja. Sa druge strane, broj grupa održavama tako da se smanjuje za
jedan prilikom svakog spajanja, što omogućava efikasno implementiranje
operacije K.
Složenost spajanja i pronalaženja predstavnika skupa je amortizovano
\(O(\alpha(n))\), gde je \(\alpha\) inverzna Ackermanova funkcija, što
je praktično konstantno za sve realistične vrednosti \(n\). Složenost operacije V a
je \(O(1)\), jer se veličina grupe
održava direktno. Složenost operacije K je takođe \(O(1)\), jer se broj grupa održava direktno.
Ukupna složenost algoritma je \(O(n +
m)\), gde su \(n\) broj ostrva,
a \(m\) broj operacija.
#include <iostream>
#include <vector>
using namespace std;
vector<int> parent;
vector<int> sz;
int groups;
void UF_init(int n)
{
parent.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i < n + 1; i++) {
parent[i] = i;
}
groups = n;
}
int UF_find(int x)
{
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void UF_union(int x, int y)
{
int fx = UF_find(x);
int fy = UF_find(y);
if (fx == fy) return;
if (sz[fx] < sz[fy]) {
swap(fx, fy);
}
parent[fy] = fx;
sz[fx] += sz[fy];
groups--;
}
bool UF_same(int x, int y)
{
return UF_find(x) == UF_find(y);
}
int UF_size_of(int x)
{
return sz[UF_find(x)];
}
int UF_size()
{
return groups;
}
int main()
{
int n, m; cin >> n >> m;
UF_init(n);
while(m--) {
char op; cin >> op;
if (op == 'U') {
int x, y; cin >> x >> y;
UF_union(x, y);
} else if (op == 'P') {
int x, y; cin >> x >> y;
cout << (UF_same(x, y) ? "DA" : "NE") << endl;
} else if (op == 'V') {
int x; cin >> x;
cout << UF_size_of(x) << endl;
} else if (op == 'K') {
cout << UF_size() << endl;
}
}
return 0;
}