Quarantraining - 02

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 :smile:

Esercizi

Connect and Disconnect - easy
Forced Online Query Problem - hard

Fonti

Deleting from a data structure in \mathcal O(T(N)\log N)

13 Mi Piace