INTRODUCERE ÎN SETUL DISJUNS (ALGORITMUL UNION-FIND)

Ce este o structură de date cu set disjunct?

Sunt numite două seturi seturi disjunse dacă nu au niciun element în comun, intersecția mulțimilor este o mulțime nulă.

O structură de date care stochează un subset de elemente care nu se suprapun sau disjunc se numește structură de date set disjunct. Structura de date a setului disjunc acceptă următoarele operații:

Adăugarea de noi seturi la setul disjunc.
Fuzionarea seturi disjunse la un singur set disjunc folosind Uniune Operațiune.
Găsirea reprezentantului unui set disjunc folosind Găsi Operațiune.
Verificați dacă două seturi sunt disjunse sau nu.

Luați în considerare o situație cu un număr de persoane și următoarele sarcini care trebuie îndeplinite asupra acestora:

Adauga o noua prietenie relație , adică o persoană x devine prietenul altei persoane, adică adăugând un nou element la un set.
Aflați dacă individual x este prieten cu individul y (prieten direct sau indirect)

Exemple:

Ni se oferă 10 indivizi spun, a, b, c, d, e, f, g, h, i, j

Următoarele sunt relațiile care trebuie adăugate:
a b
b d
c f
c i
j e
g j

Având întrebări precum dacă a este prieten cu d sau nu. Practic, trebuie să creăm următoarele 4 grupuri și să menținem o conexiune rapid accesibilă între elementele grupului:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e,g,j}
G4 = {h}

Aflați dacă x și y aparțin sau nu aceluiași grup, adică dacă x și y sunt prieteni direcți/indirecti.

Împărțirea indivizilor în seturi diferite în funcție de grupurile în care se încadrează. Această metodă este cunoscută ca a Set disjunc Uniune care mentine o colectie de Seturi disjuncte iar fiecare set este reprezentat de unul dintre membrii săi.

Pentru a răspunde la întrebarea de mai sus, două puncte cheie care trebuie luate în considerare sunt:

Cum se rezolvă seturile? Inițial, toate elementele aparțin unor seturi diferite. După ce am lucrat la relațiile date, selectăm un membru ca a reprezentant . Pot exista multe moduri de a selecta un reprezentant, una simplă este să selectezi cu cel mai mare indice.
Verificați dacă 2 persoane sunt în același grup? Dacă reprezentanții a două persoane sunt la fel, atunci vor deveni prieteni.

Structurile de date utilizate sunt:

Matrice: Se numește o matrice de numere întregi Mamă[] . Dacă avem de-a face cu N elemente, al-lea element al matricei reprezintă al-lea element. Mai precis, al i-lea element al matricei Parent[] este părintele celui de-al i-lea element. Aceste relații creează unul sau mai mulți arbori virtuali.

Copac: Este un Set disjunc . Dacă două elemente sunt în același arbore, atunci sunt în același Set disjunc . Nodul rădăcină (sau cel mai de sus) al fiecărui arbore se numește reprezentant a setului. Întotdeauna există un singur reprezentant unic a fiecărui set. O regulă simplă pentru a identifica un reprezentant este dacă „i” este reprezentantul unei mulțimi, atunci Părinte[i] = i . Dacă i nu este reprezentantul setului său, atunci poate fi găsit călătorind în sus în copac până îl găsim pe reprezentant.

Operații asupra structurilor de date cu set disjunc:

Găsi
Uniune

1. Găsiți:

Poate fi implementat prin parcurgerea recursive a matricei părinte până când atingem un nod care este părintele însuși.

C++

// Finds the representative of the set> // that i is an element of> > #include> using> namespace> std;> > int> find(>int> i)> > {> > >// If i is the parent of itself> >if> (parent[i] == i) {> > >// Then i is the representative of> >// this set> >return> i;> >}> >else> {> > >// Else if i is not the parent of> >// itself, then i is not the> >// representative of his set. So we> >// recursively call Find on its parent> >return> find(parent[i]);> >}> }> > // The code is contributed by Nidhi goel>

Java

// Finds the representative of the set> // that i is an element of> import> java.io.*;> > class> GFG {> > >static> int> find(>int> i)> > >{> > >// If i is the parent of itself> >if> (parent[i] == i) {> > >// Then i is the representative of> >// this set> >return> i;> >}> >else> {> > >// Else if i is not the parent of> >// itself, then i is not the> >// representative of his set. So we> >// recursively call Find on its parent> >return> find(parent[i]);> >}> >}> }> > // The code is contributed by Nidhi goel>

Python3

# Finds the representative of the set> # that i is an element of> > def> find(i):> > ># If i is the parent of itself> >if> (parent[i]>=>=> i):> > ># Then i is the representative of> ># this set> >return> i> >else>:> > ># Else if i is not the parent of> ># itself, then i is not the> ># representative of his set. So we> ># recursively call Find on its parent> >return> find(parent[i])> > ># The code is contributed by Nidhi goel>

C#

using> System;> > public> class> GFG{> > >// Finds the representative of the set> >// that i is an element of> >public> static> int> find(>int> i)> >{> > >// If i is the parent of itself> >if> (parent[i] == i) {> > >// Then i is the representative of> >// this set> >return> i;> >}> >else> {> > >// Else if i is not the parent of> >// itself, then i is not the> >// representative of his set. So we> >// recursively call Find on its parent> >return> find(parent[i]);> >}> >}> }>

Javascript

> // Finds the representative of the set> // that i is an element of> > function> find(i)> {> > >// If i is the parent of itself> >if> (parent[i] == i) {> > >// Then i is the representative of> >// this set> >return> i;> >}> >else> {> > >// Else if i is not the parent of> >// itself, then i is not the> >// representative of his set. So we> >// recursively call Find on its parent> >return> find(parent[i]);> >}> }> // The code is contributed by Nidhi goel> >

Complexitatea timpului : Această abordare este ineficientă și poate dura O(n) timp în cel mai rău caz.

2. Unire:

Este nevoie de două elemente ca intrare și găsește reprezentanții seturilor lor folosind Găsi operație și, în final, pune oricare dintre arbori (reprezentând setul) sub nodul rădăcină al celuilalt arbore.

C++

// Unites the set that includes i> // and the set that includes j> > #include> using> namespace> std;> > void> union>(>int> i,>int> j) {> > >// Find the representatives> >// (or the root nodes) for the set> >// that includes i> >int> irep =>this>.Find(i),> > >// And do the same for the set> >// that includes j> >int> jrep =>this>.Find(j);> > >// Make the parent of i’s representative> >// be j’s representative effectively> >// moving all of i’s set into j’s set)> >this>.Parent[irep] = jrep;> }>

Java

import> java.util.Arrays;> > public> class> UnionFind {> >private> int>[] parent;> > >public> UnionFind(>int> size) {> >// Initialize the parent array with each element as its own representative> >parent =>new> int>[size];> >for> (>int> i =>0>

; i   parent[i] = i;   }   }     // Find the representative (root) of the set that includes element i   public int find(int i) {   if (parent[i] == i) {   return i; // i is the representative of its own set   }   // Recursively find the representative of the parent until reaching the root   parent[i] = find(parent[i]); // Path compression   return parent[i];   }     // Unite (merge) the set that includes element i and the set that includes element j   public void union(int i, int j) {   int irep = find(i); // Find the representative of set containing i   int jrep = find(j); // Find the representative of set containing j     // Make the representative of i's set be the representative of j's set   parent[irep] = jrep;   }     public static void main(String[] args) {   int size = 5; // Replace with your desired size   UnionFind uf = new UnionFind(size);     // Perform union operations as needed   uf.union(1, 2);   uf.union(3, 4);     // Check if elements are in the same set   boolean inSameSet = uf.find(1) == uf.find(2);   System.out.println('Are 1 and 2 in the same set? ' + inSameSet);   }  }>

Python3

# Unites the set that includes i> # and the set that includes j> > def> union(parent, rank, i, j):> ># Find the representatives> ># (or the root nodes) for the set> ># that includes i> >irep>=> find(parent, i)> > ># And do the same for the set> ># that includes j> >jrep>=> find(parent, j)> > ># Make the parent of i’s representative> ># be j’s representative effectively> ># moving all of i’s set into j’s set)> > >parent[irep]>=> jrep>

C#

using> System;> > public> class> UnionFind> {> >private> int>[] parent;> > >public> UnionFind(>int> size)> >{> >// Initialize the parent array with each element as its own representative> >parent =>new> int>[size];> >for> (>int>

i = 0; i   {   parent[i] = i;   }   }     // Find the representative (root) of the set that includes element i   public int Find(int i)   {   if (parent[i] == i)   {   return i; // i is the representative of its own set   }   // Recursively find the representative of the parent until reaching the root   parent[i] = Find(parent[i]); // Path compression   return parent[i];   }     // Unite (merge) the set that includes element i and the set that includes element j   public void Union(int i, int j)   {   int irep = Find(i); // Find the representative of set containing i   int jrep = Find(j); // Find the representative of set containing j     // Make the representative of i's set be the representative of j's set   parent[irep] = jrep;   }     public static void Main()   {   int size = 5; // Replace with your desired size   UnionFind uf = new UnionFind(size);     // Perform union operations as needed   uf.Union(1, 2);   uf.Union(3, 4);     // Check if elements are in the same set   bool inSameSet = uf.Find(1) == uf.Find(2);   Console.WriteLine('Are 1 and 2 in the same set? ' + inSameSet);   }  }>

Javascript

// JavaScript code for the approach> > // Unites the set that includes i> // and the set that includes j> function> union(parent, rank, i, j)> {> > // Find the representatives> // (or the root nodes) for the set> // that includes i> let irep = find(parent, i);> > // And do the same for the set> // that includes j> let jrep = find(parent, j);> > // Make the parent of i’s representative> // be j’s representative effectively> // moving all of i’s set into j’s set)> > parent[irep] = jrep;> }>

Complexitatea timpului : Această abordare este ineficientă și ar putea duce la un arbore de lungime O(n) în cel mai rău caz.

Optimizări (Unirea după rang/dimensiune și comprimarea căii):

Eficiența depinde în mare măsură de ce copac se atașează de celălalt . Există 2 moduri în care se poate face. Primul este Unirea după rang, care consideră înălțimea copacului ca factor, iar al doilea este Unirea după mărime, care consideră dimensiunea copacului ca factor în timp ce atașează un copac la celălalt. Această metodă împreună cu Path Compression oferă o complexitate de timp aproape constant.

Comprimarea traseului (Modificări la Find()):

Accelerează structura datelor prin comprimarea înălțimii a copacilor. Se poate realiza prin introducerea unui mic mecanism de stocare în cache în Găsi Operațiune. Aruncă o privire la cod pentru mai multe detalii:

C++

// Finds the representative of the set that i> // is an element of.> > #include> using> namespace> std;> > int> find(>int> i)> {> > >// If i is the parent of itself> >if> (Parent[i] == i) {> > >// Then i is the representative> >return> i;> >}> >else> {> > >// Recursively find the representative.> >int> result = find(Parent[i]);> > >// We cache the result by moving i’s node> >// directly under the representative of this> >// set> >Parent[i] = result;> > >// And then we return the result> >return> result;> >}> }>

Java

// Finds the representative of the set that i> // is an element of.> import> java.io.*;> import> java.util.*;> > static> int> find(>int> i)> {> > >// If i is the parent of itself> >if> (Parent[i] == i) {> > >// Then i is the representative> >return> i;> >}> >else> {> > >// Recursively find the representative.> >int> result = find(Parent[i]);> > >// We cache the result by moving i’s node> >// directly under the representative of this> >// set> >Parent[i] = result;> > >// And then we return the result> >return> result;> >}> }> > // The code is contributed by Arushi jindal.>

Python3

# Finds the representative of the set that i> # is an element of.> > > def> find(i):> > ># If i is the parent of itself> >if> Parent[i]>=>=> i:> > ># Then i is the representative> >return> i> >else>:> > ># Recursively find the representative.> >result>=> find(Parent[i])> > ># We cache the result by moving i’s node> ># directly under the representative of this> ># set> >Parent[i]>=> result> > ># And then we return the result> >return> result> > # The code is contributed by Arushi Jindal.>

C#

cate orase SUA

using> System;> > // Finds the representative of the set that i> // is an element of.> public> static> int> find(>int> i)> {> > >// If i is the parent of itself> >if> (Parent[i] == i) {> > >// Then i is the representative> >return> i;> >}> >else> {> > >// Recursively find the representative.> >int> result = find(Parent[i]);> > >// We cache the result by moving i’s node> >// directly under the representative of this> >// set> >Parent[i] = result;> > >// And then we return the result> >return> result;> >}> }> > // The code is contributed by Arushi Jindal.>

Javascript

// Finds the representative of the set that i> // is an element of.> > > function> find(i)> {> > >// If i is the parent of itself> >if> (Parent[i] == i) {> > >// Then i is the representative> >return> i;> >}> >else> {> > >// Recursively find the representative.> >let result = find(Parent[i]);> > >// We cache the result by moving i’s node> >// directly under the representative of this> >// set> >Parent[i] = result;> > >// And then we return the result> >return> result;> >}> }> > // The code is contributed by Arushi Jindal.>

Complexitatea timpului : O(log n) în medie pe apel.

Unire după rang :

În primul rând, avem nevoie de o nouă matrice de numere întregi numite rang[] . Dimensiunea acestei matrice este aceeași cu cea a matricei părinte Mamă[] . Dacă i este reprezentantul unui set, rang[i] este înălțimea arborelui reprezentând mulțimea.
Acum amintiți-vă că în operațiunea Unirii, nu contează care dintre cei doi copaci este mutat sub celălalt. Acum ceea ce vrem să facem este să minimizăm înălțimea arborelui rezultat. Dacă unim doi copaci (sau seturi), să le numim stânga și dreapta, atunci totul depinde de rang de stânga si rang de drept .

Dacă rangul de stânga este mai mică decât rangul de dreapta , atunci cel mai bine este să te muți stânga sub dreapta , deoarece asta nu va schimba rangul dreptei (în timp ce deplasarea la dreapta sub stânga ar crește înălțimea). În același mod, dacă rangul dreptei este mai mic decât rangul stângi, atunci ar trebui să ne mișcăm dreapta sub stânga.
Dacă rangurile sunt egale, nu contează ce copac se încadrează sub celălalt, dar rangul rezultatului va fi întotdeauna cu unul mai mare decât rangul copacilor.

C++

// Unites the set that includes i and the set> // that includes j by rank> > #include> using> namespace> std;> > void> unionbyrank(>int> i,>int> j) {> > >// Find the representatives (or the root nodes)> >// for the set that includes i> >int> irep =>this>.find(i);> > >// And do the same for the set that includes j> >int> jrep =>this>.Find(j);> > >// Elements are in same set, no need to> >// unite anything.> >if> (irep == jrep)> >return>;> > >// Get the rank of i’s tree> >irank = Rank[irep],> > >// Get the rank of j’s tree> >jrank = Rank[jrep];> > >// If i’s rank is less than j’s rank> >if>

(irank     // Then move i under j   this.parent[irep] = jrep;   }     // Else if j’s rank is less than i’s rank   else if (jrank     // Then move j under i   this.Parent[jrep] = irep;   }     // Else if their ranks are the same   else {     // Then move i under j (doesn’t matter   // which one goes where)   this.Parent[irep] = jrep;     // And increment the result tree’s   // rank by 1   Rank[jrep]++;   }  }>

Java

public> class> DisjointSet {> > >private> int>[] parent;> >private> int>[] rank;> > >// Constructor to initialize the DisjointSet data> >// structure> >public> DisjointSet(>int> size)> >{> >parent =>new> int>[size];> >rank =>new> int>[size];> > >// Initialize each element as a separate set with> >// rank 0> >for> (>int> i =>0>

; i   parent[i] = i;   rank[i] = 0;   }   }     // Function to find the representative (or the root   // node) of a set with path compression   private int find(int i)   {   if (parent[i] != i) {   parent[i] = find(parent[i]); // Path compression   }   return parent[i];   }     // Unites the set that includes i and the set that   // includes j by rank   public void unionByRank(int i, int j)   {   // Find the representatives (or the root nodes) for   // the set that includes i and j   int irep = find(i);   int jrep = find(j);     // Elements are in the same set, no need to unite   // anything   if (irep == jrep) {   return;   }     // Get the rank of i's tree   int irank = rank[irep];     // Get the rank of j's tree   int jrank = rank[jrep];     // If i's rank is less than j's rank   if (irank   // Move i under j   parent[irep] = jrep;   }   // Else if j's rank is less than i's rank   else if (jrank   // Move j under i   parent[jrep] = irep;   }   // Else if their ranks are the same   else {   // Move i under j (doesn't matter which one goes   // where)   parent[irep] = jrep;   // Increment the result tree's rank by 1   rank[jrep]++;   }   }     // Example usage   public static void main(String[] args)   {   int size = 5;   DisjointSet ds = new DisjointSet(size);     // Perform some union operations   ds.unionByRank(0, 1);   ds.unionByRank(2, 3);   ds.unionByRank(1, 3);     // Find the representative of each element and print   // the result   for (int i = 0; i   System.out.println(   'Element ' + i   + ' belongs to the set with representative '  + ds.find(i));   }   }  }>

Python3

class> DisjointSet:> >def> __init__(>self>, size):> >self>.parent>=> [i>for> i>in> range>(size)]> >self>.rank>=> [>0>]>*> size> > ># Function to find the representative (or the root node) of a set> >def> find(>self>, i):> ># If i is not the representative of its set, recursively find the representative> >if> self>.parent[i] !>=> i:> >self>.parent[i]>=> self>.find(>self>.parent[i])># Path compression> >return> self>.parent[i]> > ># Unites the set that includes i and the set that includes j by rank> >def> union_by_rank(>self>, i, j):> ># Find the representatives (or the root nodes) for the set that includes i and j> >irep>=> self>.find(i)> >jrep>=> self>.find(j)> > ># Elements are in the same set, no need to unite anything> >if> irep>=>=> jrep:> >return> > ># Get the rank of i's tree> >irank>=> self>.rank[irep]> > ># Get the rank of j's tree> >jrank>=> self>.rank[jrep]> > ># If i's rank is less than j's rank> >if>

irank   # Move i under j   self.parent[irep] = jrep   # Else if j's rank is less than i's rank   elif jrank   # Move j under i   self.parent[jrep] = irep   # Else if their ranks are the same   else:   # Move i under j (doesn't matter which one goes where)   self.parent[irep] = jrep   # Increment the result tree's rank by 1   self.rank[jrep] += 1    def main(self):   # Example usage   size = 5  ds = DisjointSet(size)     # Perform some union operations   ds.union_by_rank(0, 1)   ds.union_by_rank(2, 3)   ds.union_by_rank(1, 3)     # Find the representative of each element   for i in range(size):   print(f'Element {i} belongs to the set with representative {ds.find(i)}')      # Creating an instance and calling the main method  ds = DisjointSet(size=5)  ds.main()>

C#

using> System;> > class> DisjointSet {> >private> int>[] parent;> >private> int>[] rank;> > >public> DisjointSet(>int> size) {> >parent =>new> int>[size];> >rank =>new> int>[size];> > >// Initialize each element as a separate set> >for> (>int>

i = 0; i   parent[i] = i;   rank[i] = 0;   }   }     // Function to find the representative (or the root node) of a set   private int Find(int i) {   // If i is not the representative of its set, recursively find the representative   if (parent[i] != i) {   parent[i] = Find(parent[i]); // Path compression   }   return parent[i];   }     // Unites the set that includes i and the set that includes j by rank   public void UnionByRank(int i, int j) {   // Find the representatives (or the root nodes) for the set that includes i and j   int irep = Find(i);   int jrep = Find(j);     // Elements are in the same set, no need to unite anything   if (irep == jrep) {   return;   }     // Get the rank of i's tree   int irank = rank[irep];     // Get the rank of j's tree   int jrank = rank[jrep];     // If i's rank is less than j's rank   if (irank   // Move i under j   parent[irep] = jrep;   }   // Else if j's rank is less than i's rank   else if (jrank   // Move j under i   parent[jrep] = irep;   }   // Else if their ranks are the same   else {   // Move i under j (doesn't matter which one goes where)   parent[irep] = jrep;   // Increment the result tree's rank by 1   rank[jrep]++;   }   }     static void Main() {   // Example usage   int size = 5;   DisjointSet ds = new DisjointSet(size);     // Perform some union operations   ds.UnionByRank(0, 1);   ds.UnionByRank(2, 3);   ds.UnionByRank(1, 3);     // Find the representative of each element   for (int i = 0; i   Console.WriteLine('Element ' + i + ' belongs to the set with representative ' + ds.Find(i));   }   }  }>

Javascript

// JavaScript Program for the above approach> unionbyrank(i, j) {> let irep =>this>.find(i);>// Find representative of set including i> let jrep =>this>.find(j);>// Find representative of set including j> > if> (irep === jrep) {> return>;>// Elements are already in the same set> }> > let irank =>this>.rank[irep];>// Rank of set including i> let jrank =>this>.rank[jrep];>// Rank of set including j> > if>

(irank  this.parent[irep] = jrep; // Make j's representative parent of i's representative  } else if (jrank  this.parent[jrep] = irep; // Make i's representative parent of j's representative  } else {  this.parent[irep] = jrep; // Make j's representative parent of i's representative  this.rank[jrep]++; // Increment the rank of the resulting set  }>

Unirea după mărime:

Din nou, avem nevoie de o nouă matrice de numere întregi numite mărimea[] . Dimensiunea acestei matrice este aceeași cu cea a matricei părinte Mamă[] . Dacă i este reprezentantul unui set, dimensiune[i] este numărul elementelor din arborele care reprezintă mulțimea.
Acum unim doi copaci (sau seturi), să le numim stânga și dreapta, apoi în acest caz totul depinde de dimensiunea stângii si dimensiunea dreptului copac (sau set).

Dacă dimensiunea de stânga este mai mică decât dimensiunea dreapta , atunci cel mai bine este să te muți stânga sub dreapta și măriți dimensiunea dreptei cu dimensiunea stângii. În același mod, dacă dimensiunea dreptei este mai mică decât dimensiunea stângi, atunci ar trebui să ne deplasăm la dreapta sub stânga. și măriți dimensiunea stângii cu dimensiunea dreptei.
Dacă dimensiunile sunt egale, nu contează ce copac trece sub celălalt.

C++

// Unites the set that includes i and the set> // that includes j by size> > #include> using> namespace> std;> > void> unionBySize(>int> i,>int> j) {> > >// Find the representatives (or the root nodes)> >// for the set that includes i> >int> irep = find(i);> > >// And do the same for the set that includes j> >int> jrep = find(j);> > >// Elements are in the same set, no need to> >// unite anything.> >if> (irep == jrep)> >return>;> > >// Get the size of i’s tree> >int> isize = Size[irep];> > >// Get the size of j’s tree> >int> jsize = Size[jrep];> > >// If i’s size is less than j’s size> >if>

(isize     // Then move i under j   Parent[irep] = jrep;     // Increment j's size by i's size   Size[jrep] += Size[irep];   }     // Else if j’s size is less than i’s size   else {     // Then move j under i   Parent[jrep] = irep;     // Increment i's size by j's size   Size[irep] += Size[jrep];   }  }>

Java

// Java program for the above approach> import> java.util.Arrays;> > class> UnionFind {> > >private> int>[] Parent;> >private> int>[] Size;> > >public> UnionFind(>int> n)> >{> >// Initialize Parent array> >Parent =>new> int>[n];> >for> (>int> i =>0>

; i   Parent[i] = i;   }     // Initialize Size array with 1s   Size = new int[n];   Arrays.fill(Size, 1);   }     // Function to find the representative (or the root   // node) for the set that includes i   public int find(int i)   {   if (Parent[i] != i) {   // Path compression: Make the parent of i the   // root of the set   Parent[i] = find(Parent[i]);   }   return Parent[i];   }     // Unites the set that includes i and the set that   // includes j by size   public void unionBySize(int i, int j)   {   // Find the representatives (or the root nodes) for   // the set that includes i   int irep = find(i);     // And do the same for the set that includes j   int jrep = find(j);     // Elements are in the same set, no need to unite   // anything.   if (irep == jrep)   return;     // Get the size of i’s tree   int isize = Size[irep];     // Get the size of j’s tree   int jsize = Size[jrep];     // If i’s size is less than j’s size   if (isize   // Then move i under j   Parent[irep] = jrep;     // Increment j's size by i's size   Size[jrep] += Size[irep];   }   // Else if j’s size is less than i’s size   else {   // Then move j under i   Parent[jrep] = irep;     // Increment i's size by j's size   Size[irep] += Size[jrep];   }   }  }    public class GFG {     public static void main(String[] args)   {   // Example usage   int n = 5;   UnionFind unionFind = new UnionFind(n);     // Perform union operations   unionFind.unionBySize(0, 1);   unionFind.unionBySize(2, 3);   unionFind.unionBySize(0, 4);     // Print the representative of each element after   // unions   for (int i = 0; i   System.out.println('Element ' + i   + ': Representative = '  + unionFind.find(i));   }   }  }    // This code is contributed by Susobhan Akhuli>

Python3

# Python program for the above approach> class> UnionFind:> >def> __init__(>self>, n):> ># Initialize Parent array> >self>.Parent>=> list>(>range>(n))> > ># Initialize Size array with 1s> >self>.Size>=> [>1>]>*> n> > ># Function to find the representative (or the root node) for the set that includes i> >def> find(>self>, i):> >if> self>.Parent[i] !>=> i:> ># Path compression: Make the parent of i the root of the set> >self>.Parent[i]>=> self>.find(>self>.Parent[i])> >return> self>.Parent[i]> > ># Unites the set that includes i and the set that includes j by size> >def> unionBySize(>self>, i, j):> ># Find the representatives (or the root nodes) for the set that includes i> >irep>=> self>.find(i)> > ># And do the same for the set that includes j> >jrep>=> self>.find(j)> > ># Elements are in the same set, no need to unite anything.> >if> irep>=>=> jrep:> >return> > ># Get the size of i’s tree> >isize>=> self>.Size[irep]> > ># Get the size of j’s tree> >jsize>=> self>.Size[jrep]> > ># If i’s size is less than j’s size> >if>

isize   # Then move i under j   self.Parent[irep] = jrep     # Increment j's size by i's size   self.Size[jrep] += self.Size[irep]   # Else if j’s size is less than i’s size   else:   # Then move j under i   self.Parent[jrep] = irep     # Increment i's size by j's size   self.Size[irep] += self.Size[jrep]    # Example usage  n = 5 unionFind = UnionFind(n)    # Perform union operations  unionFind.unionBySize(0, 1)  unionFind.unionBySize(2, 3)  unionFind.unionBySize(0, 4)    # Print the representative of each element after unions  for i in range(n):   print('Element {}: Representative = {}'.format(i, unionFind.find(i)))    # This code is contributed by Susobhan Akhuli>

C#

using> System;> > class> UnionFind> {> >private> int>[] Parent;> >private> int>[] Size;> > >public> UnionFind(>int> n)> >{> >// Initialize Parent array> >Parent =>new> int>[n];> >for> (>int>

i = 0; i   {   Parent[i] = i;   }     // Initialize Size array with 1s   Size = new int[n];   for (int i = 0; i   {   Size[i] = 1;   }   }     // Function to find the representative (or the root node) for the set that includes i   public int Find(int i)   {   if (Parent[i] != i)   {   // Path compression: Make the parent of i the root of the set   Parent[i] = Find(Parent[i]);   }   return Parent[i];   }     // Unites the set that includes i and the set that includes j by size   public void UnionBySize(int i, int j)   {   // Find the representatives (or the root nodes) for the set that includes i   int irep = Find(i);     // And do the same for the set that includes j   int jrep = Find(j);     // Elements are in the same set, no need to unite anything.   if (irep == jrep)   return;     // Get the size of i’s tree   int isize = Size[irep];     // Get the size of j’s tree   int jsize = Size[jrep];     // If i’s size is less than j’s size   if (isize   {   // Then move i under j   Parent[irep] = jrep;     // Increment j's size by i's size   Size[jrep] += Size[irep];   }   // Else if j’s size is less than i’s size   else  {   // Then move j under i   Parent[jrep] = irep;     // Increment i's size by j's size   Size[irep] += Size[jrep];   }   }  }    class Program  {   static void Main()   {   // Example usage   int n = 5;   UnionFind unionFind = new UnionFind(n);     // Perform union operations   unionFind.UnionBySize(0, 1);   unionFind.UnionBySize(2, 3);   unionFind.UnionBySize(0, 4);     // Print the representative of each element after unions   for (int i = 0; i   {   Console.WriteLine($'Element {i}: Representative = {unionFind.Find(i)}');   }   }  }>

Javascript

unionbysize(i, j) {> >let irep =>this>.find(i);>// Find the representative of the set containing i.> >let jrep =>this>.find(j);>// Find the representative of the set containing j.> > >if> (irep === jrep) {> >return>;>// Elements are already in the same set.> >}> > >let isize =>this>.size[irep];>// Size of the set including i.> >let jsize =>this>.size[jrep];>// Size of the set including j.> > >if>

(isize   // If i's size is less than j's size, make i's representative   // a child of j's representative.   this.parent[irep] = jrep;   this.size[jrep] += this.size[irep]; // Increment j's size by i's size.   } else {   // If j's size is less than or equal to i's size, make j's representative   // a child of i's representative.   this.parent[jrep] = irep;   this.size[irep] += this.size[jrep]; // Increment i's size by j's size.   if (isize === jsize) {   // If sizes are equal, increment the rank of i's representative.   this.rank[irep]++;   }   }   }>

Ieșire

Element 0: Representative = 0 Element 1: Representative = 0 Element 2: Representative = 2 Element 3: Representative = 2 Element 4: Representative = 0>

Complexitatea timpului : O(log n) fără compresia traseului.

Mai jos este implementarea completă a setului disjunc cu compresia traseului și unirea după rang.

C++

// C++ implementation of disjoint set> > #include> using> namespace> std;> > class> DisjSet {> >int> *rank, *parent, n;> > public>:> > >// Constructor to create and> >// initialize sets of n items> >DisjSet(>int> n)> >{> >rank =>new> int>[n];> >parent =>new> int>[n];> >this>->n = n;>>> makeSet();> >}> > >// Creates n single item sets> >void> makeSet()> >{> >for> (>int>

i = 0; i   parent[i] = i;   }   }     // Finds set of given item x   int find(int x)   {   // Finds the representative of the set   // that x is an element of   if (parent[x] != x) {     // if x is not the parent of itself   // Then x is not the representative of   // his set,   parent[x] = find(parent[x]);     // so we recursively call Find on its parent   // and move i's node directly under the   // representative of this set   }     return parent[x];   }     // Do union of two sets by rank represented   // by x and y.   void Union(int x, int y)   {   // Find current sets of x and y   int xset = find(x);   int yset = find(y);     // If they are already in same set   if (xset == yset)   return;     // Put smaller ranked item under   // bigger ranked item if ranks are   // different   if (rank[xset]   parent[xset] = yset;   }   else if (rank[xset]>rang[yset]) { părinte[yset] = xset;   } // Dacă rangurile sunt aceleași, atunci creșteți // rangul.   else { părinte[yset] = xset;   rang[xset] = rang[xset] + 1;   } } };    // Cod driver int main() { // Apel funcție DisjSet obj(5);   obj.Unire(0, 2);   obj.Unire(4, 2);   obj.Unire(3, 1);     if (obj.find(4) == obj.find(0)) cout<< 'Yes
';   else  cout << 'No
';   if (obj.find(1) == obj.find(0))   cout << 'Yes
';   else  cout << 'No
';     return 0;  }>

Java

// A Java program to implement Disjoint Set Data> // Structure.> import> java.io.*;> import> java.util.*;> > class> DisjointUnionSets {> >int>[] rank, parent;> >int> n;> > >// Constructor> >public> DisjointUnionSets(>int> n)> >{> >rank =>new> int>[n];> >parent =>new> int>[n];> >this>.n = n;> >makeSet();> >}> > >// Creates n sets with single item in each> >void> makeSet()> >{> >for> (>int> i =>0>

; i   // Initially, all elements are in   // their own set.   parent[i] = i;   }   }     // Returns representative of x's set   int find(int x)   {   // Finds the representative of the set   // that x is an element of   if (parent[x] != x) {   // if x is not the parent of itself   // Then x is not the representative of   // his set,   parent[x] = find(parent[x]);     // so we recursively call Find on its parent   // and move i's node directly under the   // representative of this set   }     return parent[x];   }     // Unites the set that includes x and the set   // that includes x   void union(int x, int y)   {   // Find representatives of two sets   int xRoot = find(x), yRoot = find(y);     // Elements are in the same set, no need   // to unite anything.   if (xRoot == yRoot)   return;     // If x's rank is less than y's rank   if (rank[xRoot]     // Then move x under y so that depth   // of tree remains less   parent[xRoot] = yRoot;     // Else if y's rank is less than x's rank   else if (rank[yRoot]     // Then move y under x so that depth of   // tree remains less   parent[yRoot] = xRoot;     else // if ranks are the same   {   // Then move y under x (doesn't matter   // which one goes where)   parent[yRoot] = xRoot;     // And increment the result tree's   // rank by 1   rank[xRoot] = rank[xRoot] + 1;   }   }  }    // Driver code  public class Main {   public static void main(String[] args)   {   // Let there be 5 persons with ids as   // 0, 1, 2, 3 and 4   int n = 5;   DisjointUnionSets dus =   new DisjointUnionSets(n);     // 0 is a friend of 2   dus.union(0, 2);     // 4 is a friend of 2   dus.union(4, 2);     // 3 is a friend of 1   dus.union(3, 1);     // Check if 4 is a friend of 0   if (dus.find(4) == dus.find(0))   System.out.println('Yes');   else  System.out.println('No');     // Check if 1 is a friend of 0   if (dus.find(1) == dus.find(0))   System.out.println('Yes');   else  System.out.println('No');   }  }>

Python3

# Python3 program to implement Disjoint Set Data> # Structure.> > class> DisjSet:> >def> __init__(>self>, n):> ># Constructor to create and> ># initialize sets of n items> >self>.rank>=> [>1>]>*> n> >self>.parent>=> [i>for> i>in> range>(n)]> > > ># Finds set of given item x> >def> find(>self>, x):> > ># Finds the representative of the set> ># that x is an element of> >if> (>self>.parent[x] !>=> x):> > ># if x is not the parent of itself> ># Then x is not the representative of> ># its set,> >self>.parent[x]>=> self>.find(>self>.parent[x])> > ># so we recursively call Find on its parent> ># and move i's node directly under the> ># representative of this set> > >return> self>.parent[x]> > > ># Do union of two sets represented> ># by x and y.> >def> Union(>self>, x, y):> > ># Find current sets of x and y> >xset>=> self>.find(x)> >yset>=> self>.find(y)> > ># If they are already in same set> >if> xset>=>=> yset:> >return> > ># Put smaller ranked item under> ># bigger ranked item if ranks are> ># different> >if> self>.rank[xset] <>self>.rank[yset]:> >self>.parent[xset]>=> yset> > >elif> self>.rank[xset]>>>>.rank[yset]:> >self>.parent[yset]>=> xset> > ># If ranks are same, then move y under> ># x (doesn't matter which one goes where)> ># and increment rank of x's tree> >else>:> >self>.parent[yset]>=> xset> >self>.rank[xset]>=> self>.rank[xset]>+> 1> > # Driver code> obj>=> DisjSet(>5>)> obj.Union(>0>,>2>)> obj.Union(>4>,>2>)> obj.Union(>3>,>1>)> if> obj.find(>4>)>=>=> obj.find(>0>):> >print>(>'Yes'>)> else>:> >print>(>'No'>)> if> obj.find(>1>)>=>=> obj.find(>0>):> >print>(>'Yes'>)> else>:> >print>(>'No'>)> > # This code is contributed by ng24_7.>

C#

// A C# program to implement> // Disjoint Set Data Structure.> using> System;> > class> DisjointUnionSets> {> >int>[] rank, parent;> >int> n;> > >// Constructor> >public> DisjointUnionSets(>int> n)> >{> >rank =>new> int>[n];> >parent =>new> int>[n];> >this>.n = n;> >makeSet();> >}> > >// Creates n sets with single item in each> >public> void> makeSet()> >{> >for> (>int>

i = 0; i   {   // Initially, all elements are in   // their own set.   parent[i] = i;   }   }     // Returns representative of x's set   public int find(int x)   {   // Finds the representative of the set   // that x is an element of   if (parent[x] != x)   {     // if x is not the parent of itself   // Then x is not the representative of   // his set,   parent[x] = find(parent[x]);     // so we recursively call Find on its parent   // and move i's node directly under the   // representative of this set   }   return parent[x];   }     // Unites the set that includes x and   // the set that includes x   public void union(int x, int y)   {   // Find representatives of two sets   int xRoot = find(x), yRoot = find(y);     // Elements are in the same set,   // no need to unite anything.   if (xRoot == yRoot)   return;     // If x's rank is less than y's rank   if (rank[xRoot]     // Then move x under y so that depth   // of tree remains less   parent[xRoot] = yRoot;     // Else if y's rank is less than x's rank   else if (rank[yRoot]     // Then move y under x so that depth of   // tree remains less   parent[yRoot] = xRoot;     else // if ranks are the same   {   // Then move y under x (doesn't matter   // which one goes where)   parent[yRoot] = xRoot;     // And increment the result tree's   // rank by 1   rank[xRoot] = rank[xRoot] + 1;   }   }  }    // Driver code  class GFG  {   public static void Main(String[] args)   {   // Let there be 5 persons with ids as   // 0, 1, 2, 3 and 4   int n = 5;   DisjointUnionSets dus =   new DisjointUnionSets(n);     // 0 is a friend of 2   dus.union(0, 2);     // 4 is a friend of 2   dus.union(4, 2);     // 3 is a friend of 1   dus.union(3, 1);     // Check if 4 is a friend of 0   if (dus.find(4) == dus.find(0))   Console.WriteLine('Yes');   else  Console.WriteLine('No');     // Check if 1 is a friend of 0   if (dus.find(1) == dus.find(0))   Console.WriteLine('Yes');   else  Console.WriteLine('No');   }  }    // This code is contributed by Rajput-Ji>

Javascript

class DisjSet {> >constructor(n) {> >this>.rank =>new> Array(n);> >this>.parent =>new> Array(n);> >this>.n = n;> >this>.makeSet();> >}> > >makeSet() {> >for> (let i = 0; i <>this>.n; i++) {> >this>.parent[i] = i;> >}> >}> > >find(x) {> >if> (>this>.parent[x] !== x) {> >this>.parent[x] =>this>.find(>this>.parent[x]);> >}> >return> this>.parent[x];> >}> > >Union(x, y) {> >let xset =>this>.find(x);> >let yset =>this>.find(y);> > >if> (xset === yset)>return>;> > >if> (>this>.rank[xset] <>this>.rank[yset]) {> >this>.parent[xset] = yset;> >}>else> if> (>this>.rank[xset]>>>>.rank[yset]) {> >this>.parent[yset] = xset;> >}>else> {> >this>.parent[yset] = xset;> >this>.rank[xset] =>this>.rank[xset] + 1;> >}> >}> }> > // usage example> let obj =>new> DisjSet(5);> obj.Union(0, 2);> obj.Union(4, 2);> obj.Union(3, 1);> > if> (obj.find(4) === obj.find(0)) {> >console.log(>'Yes'>);> }>else> {> >console.log(>'No'>);> }> if> (obj.find(1) === obj.find(0)) {> >console.log(>'Yes'>);> }>else> {> >console.log(>'No'>);> }>

Ieșire

Yes No>

Complexitatea timpului : O(n) pentru crearea a n seturi de articole unice . Cele două tehnici -comprimarea traseului cu unirea după rang/mărime, complexitatea timpului va atinge un timp aproape constant. Se pare că finala complexitatea timpului amortizat este O(α(n)), unde α(n) este funcția Ackermann inversă, care crește foarte constant (nu depășește nici măcar pentru n<10⁶⁰⁰aproximativ).

Complexitatea spațiului: O(n) deoarece trebuie să stocăm n elemente în Structura de date a setului disjunct.

Ce este o structură de date cu set disjunct?

Aflați dacă x și y aparțin sau nu aceluiași grup, adică dacă x și y sunt prieteni direcți/indirecti.

Structurile de date utilizate sunt:

Operații asupra structurilor de date cu set disjunc:

1. Găsiți:

C++

Java

Python3

C#

Javascript

2. Unire:

C++

Java

Python3

C#

Javascript

Optimizări (Unirea după rang/dimensiune și comprimarea căii):

Comprimarea traseului (Modificări la Find()):

C++

Java

Python3

C#

Javascript

Unire după rang :

C++

Java

Python3

C#

Javascript

Unirea după mărime:

C++

Java

Python3

C#

Javascript

Mai jos este implementarea completă a setului disjunc cu compresia traseului și unirea după rang.

C++

Java

Python3

C#

Javascript