Clasa a 7-a Lecția 27: Algoritmul Union-Find

Înregistrare video lecție

Load video

YouTube

YouTube might collect personal data. Privacy Policy

ContinueDismiss

Problema Disjoint

Se dau N mulţimi de numere, iniţial fiecare mulţime i conţinând un singur element, mai exact elementul i. Asupra acestor mulţimi se pot face 2 tipuri de operaţii, astfel:

• operaţia de tipul 1: se dau două numere naturale x si y, între 1 şi N. Se cere să se reunească mulţimile în care se află elementul x, respectiv elementul y (se garantează că x si y nu se vor afla în aceeaşi mulţime).
• operaţia de tipul 2: se dau două numere naturale x si y, între 1 şi N. Se cere să se afişeze DA dacă cele 2 elemente se află în aceeaşi mulţime, respectiv NU în caz contrar.

Date de intrare

Pe prima linie a fişierului de intrare disjoint.in se vor afla 2 numere, N şi M, reprezentând numărul de mulţimi, respectiv numărul de operaţii efectuate. Pe următoarele M linii se vor afla câte 3 numere, cod, x si y, cod reprezentând tipul operaţiei, iar x si y având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire disjoint.out se vor afişa mai multe linii, fiecare linie conţinând DA sau NU, reprezentând răspunsul la interogarea corespunzătoare din fişierul de intrare.

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 100 000

Exemplu

disjoint.in	disjoint.out
4 6 1 1 2 1 3 4 2 1 3 2 1 2 1 1 3 2 1 4	NU DA DA

Algoritmul union-find

Problema Disjoint şi rezolvarea ei, este o unealtă foarte utilă din trusa de scule a algoritmistului. Să definim problema:

Dată o mulţime A de valori de la 0 la N-1 definim submulţimi disjuncte pe această mulţime, astfel încât aceste submulţimi să acopere mulţimea originală A. Apoi începem să reunim unele dintre aceste mulţimi. Reuniunea se face menţionând două elemente ale submulţimilor ce se doresc reunite (dacă elementele se găsesc deja în aceeaşi submulţime nu vom face nimic). După ce efectuăm aceste operaţii de reuniune dorim să răspundem la întrebarea ce submulţimi avem?.

Cu alte cuvinte, cunoscând N şi ştiind că iniţial fiecare număr face parte din propria submulţime şi apoi dându-se mai multe perechi de numere (a_i, a_j) cu semnificaţia mulţimea din care face parte ai se reuneşte cu mulţimea din care face parte a_j trebuie ca în final să spunem ce submulţimi există.

Pentru a implementa algoritmul vom avea nevoie de două operaţii:

• reuneşte două mulţimi (union)
• găseşte mulţimea unui element (find)

De aici şi denumirea problemei union-find. În română se regăseşte sub numele de colecţie de mulţimi disjuncte, dar se folosesc și denumirile DSU (disjoint set union) sau union-find.

Soluție forță brută

O soluție posibilă ar fi ca pentru fiecare număr i să memorăm mulțimea din care face el parte. Astfel, m[i] va conține numărul mulțimii lui i. Dacă i și j fac parte din aceeași mulțime atunci m[i] = m[j], în caz contrar m[i] ≠ m[j].

Inițial fiecare număr va avea propria lui mulțime, adică m[i] = i.

Operația Find

Precum am spus, find(i) ne va da un identificator unic al mulțimii elementului i. În cazul nostru el va fi un număr între 0 și N-1. Cum o implementăm? Returnând chiar m[i]!

int find( int i ) {
  return m[i];
}

Ce complexitate are această operație?

Desigur O(1).

Operația Union

Operația union(i, j) trebuie să reunească mulțimile din care fac parte elementele i, respectiv j. Cum o implementăm? Suprascriind identificatorul mulțimii lui j cu identificatorul mulțimii lui i, peste tot unde apare el.

void union( int i, int j ) {
  int k, mj = m[j];

  for ( k = 0; k < N; k++ )
    if ( m[k] == mj )
      m[k] = m[i];
}

Ce complexitate are această operație?

Desigur O(N).

Concluzie

Cu forța brută vom avea complexitățile:

• Find: O(1) timp.
• Union: O(N) timp.
• Memorie necesară: O(N).

Soluție alternativă

Să încercăm să optimizăm operația union. Actualizarea identificatorilor mulțimii durează mult. Ce putem face?

O idee ar fi ca, în loc să actualizăm toți identificatorii mulțimii lui j, să îl actualizăm doar pe al lui j. Astfel, fiecare element între 0 și N-1 va ţine mine un şef al său din mulţime. Întocmai ca într-o companie, fiecare element al unei submulţimi va raporta unui şef, şefii vor raporta altor şefi şi aşa mai departe până ce se ajunge la şeful unic, conducătorul submulţimii. El nu are şef şi este considerat reprezentantul acelei submulţimi.

Cum memorăm acest lucru? Printr-un simplu vector de şefi (similar vectorului m[]) în care elementul sef[i] este numărul din mulţimea 0..N-1 care este şeful lui i. Ce punem în elementele şefi supremi, cele care nu au șefi? Pentru a le distinge de elementele subalterni fiecare şef suprem este propriul lui şef. Dacă elementul i este şef suprem atunci sef[i] = i. O alternativă la această reprezentare, dacă sacrificăm elementul 0, este să memorăm zero ca şef fictiv pentru elementele reprezentative ale mulţimilor.

Inițial fiecare element este propriul său șef. Atunci când căutăm o mulțime, căutăm de fapt șeful suprem, care este propriul său șef. Când unificăm mulțimile lui i și ale lui j vom nota că șeful mulțimii i devine șeful șefului mulțimii j.

Operația Find

Precum am spus, find(i) va returna șeful mulțimii din care face parte i. Cum îl găsim? Mergând la șeful lui i, apoi la șeful șefului lui i și tot așa până la șeful mulțimii. Iată o implementare recursivă simplă:

int find( int i ) {
  if ( sef[i] == i )     // daca am gasit seful suprem
    return i;            // il returnam
  return find( sef[i] ); // altfel returnam seful sefului
}

Ce complexitate are această operație?

Care este cazul cel mai rău? Când toate elementele se înșiră într-un lanț lung de șefi. În acest caz timpul este O(N).

Operația Union

Operația union(i, j) trebuie să reunească mulțimile din care fac parte elementele i, respectiv j. Cum o implementăm? Suprascriind identificatorul mulțimii lui j cu identificatorul mulțimii lui i, peste tot unde apare el.

void union( int i, int j ) {
  int sefi, sefj;

  sefi = find( i ); // seful suprem al lui i
  sefj = find( j ); // seful suprem al lui j

  sef[sefj] = sefi; // seful suprem al lui sefj devine sefi
}

Ce complexitate are această operație?

Ea apelează de două ori find(), iar apoi face O(1) operații.

Concluzie

Cu soluția alternativă avem complexitățile:

• Find: O(N) timp.
• Union: O(1) timp + complexitatea lui Find.
• Memorie necesară: O(N).

Nu pare că am avansat, nu? Poate că nu. Observăm, însă, că timpul total depinde de Find: dacă reușim să îmbunătățim complexitatea lui Find automat vom îmbunătăți și complexitatea lui Union.

Putem îmbunătăți timpul lui find la O(log N) cu o modificare destul de mică a structurii de date, dar nu voi prezenta acest lucru. Pentru cei curioși, putem memora cea mai lungă cale de șefi din fiecare mulțime, iar apoi vom atașa mulțimea mai mică la cea mai mare (alegând în mod potrivit dacă atașăm șeful lui i la j sau invers).

Soluție eficientă folosind compresia căii

Pentru a obţine cel mai eficient algoritm cunoscut avem nevoie de două optimizări: compresia căii și menținerea unui rang al fiecărei mulțimi. Voi prezenta aici doar una dintre ele, cea mai importantă, compresia căii. Ea face un lucru foarte simplu: schimbă puţin funcţia find ca, atunci când dorim să aflăm care este şeful nodului i, să lege toţi şefii parcurşi direct la şeful suprem. Cu alte cuvinte vom parcurge aceiaşi şefi intermediari până la şeful suprem, dar odată găsit va trebui să ne întoarcem la şefii intermediari şi să le schimbăm şeful. Aceasta duce aproximativ la o dublare a opreaţiilor efectuate de find. Dar, precum spunea astronatul Neil Armstrong, un pas mic pentru un om poate fi un pas uriaş pentru omenire. O mică modificare ce duce la dublarea timpului lui find duce la o scurtare fantastică a următoarelor operaţiuni find.

Exemplu de find cu compresia căii

Această optimizare poartă denumirea de compresia căii, sau, în engleză, path compression.

Operația Find

Iată o modificare mică a funcției anterioare, care face și compresia căii:

int find( int i ) {
  if ( sef[i] == i )   // daca am gasit seful suprem
    return i;          // il returnam
  return sef[i] = find( sef[i] ); // altfel legam i la seful suprem, pe care il si returnam
}

Operația Union

Operația union(i, j) trebuie să reunească mulțimile din care fac parte elementele i, respectiv j. Cum o implementăm? Suprascriind identificatorul mulțimii lui j cu identificatorul mulțimii lui i, peste tot unde apare el.

void union( int i, int j ) {
  int sefi, sefj;

  sefi = find( i ); // seful suprem al lui i
  sefj = find( j ); // seful suprem al lui j

  sef[sefj] = sefi; // seful suprem al lui sefj devine sefi
}

Ce complexitate au aceste operații?

În această implementare, ele sunt O(log N) amortizat, per operație, cu o constantă foarte mică. Demonstrația acestui lucru depășește cadrul acestui curs.

Concluzie

Cu compresia căii avem complexitățile:

• Find: O(log N) timp.
• Union: O(log N) timp.
• Memorie necesară: O(N).

Notă: se poate mai bine. Dacă adăugăm și cealaltă optimizare menționată mai sus, rangul unei mulțimi, ajungem la o complexitate O(α(N)), unde α(N) este inversul funcției lui Ackermann, o funcție rapid crescătoare. Cu această modificare timpul amortizat este, practic, constant.

Inversarea sensului

Ocazional veți întâlni problema inversă: se pornește cu o structură conexă care, treptat, este deconectată. Pe parcurs, se cer informații despre conexitate. Aceasta este o problemă de partiționare, care nu admite o soluție directă la fel de simplă.

Dar, când memoria permite stocarea șirului de operații, o soluție este:

• Executăm toate operațiile de deconectare, obținând structura finală.
• Executăm în ordine inversă operațiile, care acum reconectează structura. Putem face aceste operații cu structuri de mulțimi disjuncte.
• Notăm răspunsurile la interogările de conexitate.
• Tipărim aceste răspunsuri în ordine inversă.

Exemple de astfel de probleme: Bile3, Ruine, pe care le aveți la temă, respectiv tema opțională.

Tema 27

Să se rezolve următoarele probleme (program C trimis la NerdArena):

• Disjoint
• Channels dată la Shumen 2012 juniori
• Bile3

Tema opțională

Să se rezolve următoarele probleme (program C trimis la NerdArena):

• Flota
• Ruine

Accesează rezolvarea temei 29