Păduri de mulțimi disjuncte

Această structură arborescentă permite să păstrăm informații despre modul în care sunt grupate nodurile unui graf în componente conexe (sau nodurile unei mulțimi în submulțimi).

Nu ne ne ajută să spunem dacă două noduri sunt sau nu legate prin muchie, dar ne permite să aflăm ușor dacă două noduri sunt sau nu în aceeași componentă conexă.

Permite operații de actualizare și interogare în timp logaritmic.

Folosind tehnici precum compresia drumului putem ajunge să facem operațiile cu timp de calcul constant, amortizat.

Structura este utilă și la probleme pentru care asocierea cu grafurile este mai puțin vizibilă. Se vor întâlni astfel de situații între problemele propuse.