Na arheološkom nalazištu postoji \(N\) prostorija, numerisanih od \(0\) do \(N−1\). Tokom istraživanja događaju se dva tipa operacija:
Otkrivanje tunela: arheolozi pronalaze novi tunel koji povezuje prostorije \(x\) i \(y\). Od tog trenutka, ne samo da je moguće ići direktno iz \(x\) u \(y\), već se spajaju i svi ranije dostupni putevi iz \(x\) i svi ranije dostupni putevi iz \(y\). Drugim rečima, posle ovog otkrića može se prolaziti između bilo koje prostorije koja je već bila povezana sa \(x\) i bilo koje prostorije koja je već bila povezana sa \(y\).
Provera prolaza: arheolozi žele da znaju da li trenutno postoji put od prostorije \(x\) do prostorije \(y\) kroz otkrivene tunele.
Na osnovu hronološkog zapisa ovih događaja potrebno je odgovoriti na sva pitanja o prohodnosti.
Sa standardnog ulaza se unose vrednosti \(N\) i \(M\) koje predstavljaju broj prostorija i broj hodnika redom. U sledećih \(M\) linija se unose se upiti 2 vrste:
\(T\) \(x\) \(y\) - pronađen je tunel između prostorija \(x\) i \(y\)
\(Q\) \(x\) \(y\) - postavlja se pitanje da li postoji put od prostorije \(x\) do prostorije \(y\)
Za svaki \(Q\) upit ispisati \(DA\) ako postoji put, ili \(NE\) ako ne postoji.
5 10 T 0 4 T 1 0 T 4 2 T 4 1 Q 2 3 Q 2 1 T 3 0 Q 0 2 Q 3 0 Q 0 1
NE DA DA DA DA
Rešenje koristi osnovnu implementaciju strukture disjunktnih skupova (Union-Find) sa optimizacijama: kompresija puta i spajanje po rangu.
Svaka operacija se izvršava u amortizovanoj složenosti \(O(\alpha(N))\) (gde je \(\alpha\) inverzna Ackermanova funkcija), što je praktično konstantno za sve realistične vrednosti \(N\). Ukupna složenost algoritma je \(O(N + M)\).
#include <iostream>
#include <vector>
using namespace std;
vector<int> parent;
vector<int> rang;
void UF_init(int n)
{
parent.resize(n);
rang.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rang[i] = 0;
}
}
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 (rang[fx] < rang[fy]) {
parent[fx] = fy;
} else if (rang[fy] < rang[fx]) {
parent[fy] = fx;
} else {
parent[fx] = fy;
rang[fy]++;
}
}
int main()
{
int n, q;
cin >> n >> q;
UF_init(n);
while (q--) {
char op; int x, y;
cin >> op >> x >> y;
if (op == 'T') {
UF_union(x, y);
} else { // op == 'Q'
if (UF_find(x) == UF_find(y)) {
cout << "DA" << endl;
} else {
cout << "NE" << endl;
}
}
}
return 0;
}