Dynamic connectivity
Prerequisiti
- Union-find disjoint set
- Segment tree
- Risolvere un problema offline
Problema
Viene dato un grafo con N nodi (N \le 10^5) inizialmente vuoto e Q query (Q \le 10^5). Le query sono di 3 tipi:
- Aggiungere un arco da u a v
- Togliere un arco da u a v
- Controllare se esiste un percorso tra i nodi u e v
Soluzione
Possiamo risolvere efficientemente questo problema offline con complessità \mathcal O(Q\cdot \log Q \cdot \log N).
Se nel problema non ci fosse l’operazione di rimozione di un arco si potrebbe risolvere il problema attraverso gli UFDS. Per risolvere il problema generale bisogna prima aggiungere l’operazione di rollback, ovvero di annullare l’ultima operazione eseguita. Possiamo implementarla salvandoci la cronologia delle operazioni eseguite.
vector<pair<int, int>> history;
int parent[MAXN];
int size[MAXN];
void init() {
iota(parent, parent + MAXN, 0);
fill(size, size + MAXN, 1);
}
int find(int v) { // senza la path-compression
if (parent[v] == v) return v;
return find(parent[v]);
}
bool merge(int v, int u) {
v = find(v), u = find(u);
if (v == u) return false;
if (size[v] < size[u]) swap(v, u);
parent[u] = v;
size[v] += size[u];
history.emplace_back(v, u);
return true;
}
void rollback() {
auto [v, u] = history.back();
history.pop_back();
size[v] -= size[u];
parent[u] = u;
}
L’idea per risolvere il problema è di creare una linea del tempo nella quale rappresentiamo tutte le query, l’i-esima query viene effettuata all’istante i. In questo modo possiamo rappresentare un arco come un serie di intervalli [a, b] che indicano che l’arco è stato aggiunto all’istante a ed è stato rimosso all’istante b, se l’arco non viene rimosso allora b = Q. Notiamo che il numero totale di intervalli è \mathcal O(Q).
Con questa idea possiamo costruire un segment tree sul tempo, se un nodo dell’albero rappresenta un intervallo [l, r] allora in quel nodo ci saranno tutti gli archi presenti nell’intero intervallo di tempo [l, r]. Se un arco appartiene ad un intervallo di tempo [a, b], l’intervallo verrà spezzato in \mathcal O(\log Q) nodi del segment tree. Le foglie del segment tree rappresentano invece le query del terzo tipo.
Per risolvere il problema per prima cosa bisogna calcolare tutti gli intervalli di tempo degli archi offline, poi possiamo processare gli eventi raggruppandoli in intervalli di tempo, partendo da dall’intervallo di tempo [0, Q]. Per processare un intervallo per prima cosa aggiungiamo tutti gli archi appartenenti a tale intervallo, poi risolviamo il problema ricorsivamente nei due figli del nodo e infine rimuoviamo gli archi aggiunti, quando raggiungiamo una foglia rispondiamo a tutte le query del terzo tipo in quella foglia.
vector<pair<int, int>> edge[4 * MAXQ]; // (v, u)
array<int, 3> query[4 * MAXQ]; // (indice, v, u)
bool answer[MAXQ];
void solve(int l, int r, int p) { // intervallo [l, r)
if (l + 1 == r) { // se il nodo è una foglia
auto [i, v, u] : query[p];
if (i != -1) { // se esiste una query nella foglia
answer[i] = (find(v) == find(u));
}
return;
}
int cnt = 0; // numero di archi aggiunti
for (auto [v, u] : edge[p]) { // aggiungo gli archi
cnt += merge(v, u);
}
int m = (l + r);
solve(l, m, 2 * p);
solve(m, r, 2 * p + 1);
for (int i = 0; i < cnt; i++) { // rimuovo gli archi aggiunti
rollback();
}
}
Dato che ci sono \mathcal O(Q) intervalli distinti, il numero totale di archi è \mathcal O(Q\cdot \log Q) e perciò la complessità finale è \mathcal O(Q\cdot \log Q\cdot \log N).
Conclusioni
Possiamo estendere questa tecnica a qualsiasi struttura dati che non supporti l’operazione di rimozione aggiungendo un fattore \mathcal O(\log Q) alla complessità finale. Da notare che questa tecnica non funziona se l’inserimento avviene con complessità ammortizzata.
Per chiarimenti o domande chiedete pure
Esercizi
Connect and Disconnect - easy
Forced Online Query Problem - hard