INLEIDING TOT DISJUNCTE VERZAMELINGEN (UNION-FIND-ALGORITME)

Wat is een disjuncte verzameling datastructuur?

Er worden twee sets genoemd onsamenhangende verzamelingen als ze geen enkel element gemeen hebben, is het snijpunt van sets een nulset.

Een datastructuur die niet-overlappende of onsamenhangende subsets van elementen opslaat, wordt disjuncte set-datastructuur genoemd. De disjuncte verzameling datastructuur ondersteunt de volgende bewerkingen:

Nieuwe verzamelingen toevoegen aan de disjuncte verzameling.
Het samenvoegen van disjuncte sets tot een enkele disjuncte set met behulp van Unie operatie.
Representatief zoeken voor een disjuncte verzameling met behulp van Vinden operatie.
Controleer of twee sets disjunct zijn of niet.

Beschouw een situatie met meerdere personen en de volgende taken die daarop moeten worden uitgevoerd:

Voeg een ... toe nieuwe vriendschap relatie , dat wil zeggen dat een persoon x de vriend wordt van een andere persoon y, dat wil zeggen dat hij een nieuw element aan een set toevoegt.
Zoek of het individueel is x is een vriend van individu y (directe of indirecte vriend)

Voorbeelden:

We krijgen 10 individuen, zeg: a, b, c, d, e, f, g, h, i, j

Hieronder volgen relaties die moeten worden toegevoegd:
een b
b d
cf
c ik
j e
g j

Gegeven vragen zoals of a een vriend is van d of niet. We moeten in principe de volgende vier groepen creëren en een snel toegankelijke verbinding tussen groepsitems onderhouden:
G1 = {a, b, d}
G2 = {c, f, ik}
G3 = {e,g,j}
G4 = {u}

Ontdek of x en y tot dezelfde groep behoren of niet, d.w.z. of x en y directe/indirecte vrienden zijn.

Het verdelen van de individuen in verschillende sets, afhankelijk van de groepen waarin ze vallen. Deze methode staat bekend als a Onsamenhangende verzameling Unie die een verzameling onderhoudt Onsamenhangende sets en elke set wordt vertegenwoordigd door een van zijn leden.

Om de bovenstaande vraag te beantwoorden, zijn er twee belangrijke punten waarmee rekening moet worden gehouden:

Hoe sets op te lossen? Aanvankelijk behoren alle elementen tot verschillende sets. Nadat we aan de gegeven relaties hebben gewerkt, selecteren we een lid als vertegenwoordiger . Er kunnen veel manieren zijn om een vertegenwoordiger te selecteren. Een eenvoudige manier is om met de grootste index te selecteren.
Controleer of 2 personen in dezelfde groep zitten? Als vertegenwoordigers van twee individuen hetzelfde zijn, worden ze vrienden.

Gebruikte datastructuren zijn:

Array: Er wordt een array van gehele getallen aangeroepen Ouder[] . Als we te maken hebben met N items, vertegenwoordigt het i-de element van de array het i-de item. Preciezer gezegd: het i-de element van de Parent[]-array is de ouder van het i-de item. Deze relaties creëren een of meer virtuele bomen.

Boom: Het is een Onsamenhangende set . Als twee elementen zich in dezelfde boom bevinden, bevinden ze zich in dezelfde boom Onsamenhangende set . Het hoofdknooppunt (of het bovenste knooppunt) van elke boom wordt de vertegenwoordiger van het stel. Er is altijd één unieke vertegenwoordiger van elke set. Een eenvoudige regel om een vertegenwoordiger te identificeren is of 'i' de vertegenwoordiger van een verzameling is Ouder[i] = ik . Als i niet de vertegenwoordiger van zijn groep is, kan deze worden gevonden door de boom op te reizen totdat we de vertegenwoordiger vinden.

Bewerkingen op disjuncte set-datastructuren:

Vinden
Unie

1. Zoek:

Kan worden geïmplementeerd door de ouderarray recursief te doorlopen totdat we een knooppunt tegenkomen dat de ouder van zichzelf is.

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

Tijdcomplexiteit : Deze aanpak is inefficiënt en kan in het ergste geval O(n) tijd in beslag nemen.

2. Unie:

Het duurt twee elementen als invoer en vindt de vertegenwoordigers van hun sets met behulp van de Vinden en plaatst uiteindelijk een van de bomen (die de set vertegenwoordigen) onder het hoofdknooppunt van de andere boom.

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;> }>

Tijdcomplexiteit : Deze aanpak is inefficiënt en zou in het ergste geval kunnen leiden tot een boom met lengte O(n).

Optimalisaties (vereniging op rang/grootte en padcompressie):

De efficiëntie hangt sterk af van welke boom aan de andere gehecht raakt . Er zijn 2 manieren waarop dit kan worden gedaan. De eerste is Union by Rank, waarbij de hoogte van de boom als de factor wordt beschouwd, en de tweede is Union by Size, waarbij de grootte van de boom als de factor wordt beschouwd bij het koppelen van de ene boom aan de andere. Deze methode, samen met Path Compression, zorgt voor een complexiteit van vrijwel constante tijd.

Padcompressie (Aanpassingen aan Find()):

Het versnelt de datastructuur door het comprimeren van de hoogte van de bomen. Dit kan worden bereikt door een klein caching-mechanisme in de Vinden operatie. Bekijk de code voor meer details:

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#

verborgen apps

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.>

Tijdcomplexiteit : O(log n) gemiddeld per gesprek.

Unie op rang :

Allereerst hebben we een nieuwe reeks gehele getallen nodig, genaamd rang[] . De grootte van deze array is hetzelfde als die van de bovenliggende array Ouder[] . Als i representatief is voor een verzameling, rang[ik] is de hoogte van de boom die de set vertegenwoordigt.
Bedenk nu dat het bij de Union-operatie niet uitmaakt welke van de twee bomen onder de andere wordt verplaatst. Wat we nu willen doen is de hoogte van de resulterende boom minimaliseren. Als we twee bomen (of sets) verenigen, laten we ze links en rechts noemen, dan hangt het allemaal af van de rang van links en de rang van rechts .

Als de rang van links is lager dan de rang van rechts , dan kun je het beste verhuizen links onder rechts , omdat dat de rangorde van rechts niet verandert (terwijl het verplaatsen van rechts onder links de hoogte zou vergroten). Op dezelfde manier, als de rang van rechts lager is dan de rang van links, dan moeten we rechts onder links gaan.
Als de rangen gelijk zijn, maakt het niet uit welke boom onder de andere komt, maar de rang van het resultaat zal altijd één hoger zijn dan de rang van de bomen.

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  }>

Unie op maat:

Nogmaals, we hebben een nieuwe reeks gehele getallen nodig, genaamd maat[] . De grootte van deze array is hetzelfde als die van de bovenliggende array Ouder[] . Als i representatief is voor een verzameling, maat[ik] is het aantal elementen in de boom die de set vertegenwoordigen.
Nu verenigen we twee bomen (of sets), laten we ze links en rechts noemen, dan hangt het in dit geval allemaal af van de maat links en de maat rechts boom (of set).

Als de grootte van links is kleiner dan de grootte van rechts , dan kun je het beste verhuizen links onder rechts en vergroot de grootte van rechts met de grootte van links. Op dezelfde manier, als de grootte van rechts kleiner is dan de grootte van links, moeten we rechts onder links bewegen. en vergroot de grootte van links met de grootte van rechts.
Als de maten gelijk zijn, maakt het niet uit welke boom onder de andere komt.

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]++;   }   }   }>

Uitvoer

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

Tijdcomplexiteit : O(log n) zonder padcompressie.

Hieronder vindt u de volledige implementatie van een disjuncte set met padcompressie en unie op 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]) { ouder[yset] = xset;   } // Als de rangen hetzelfde zijn, verhoog dan // de rang.   anders { ouder[yset] = xset;   rang[xset] = rang[xset] + 1;   } } };    // Stuurprogrammacode int main() {// Functieaanroep DisjSet obj(5);   obj.Unie(0, 2);   obj.Unie(4, 2);   obj.Unie(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]>>self>.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]>>this>.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'>);> }>

Uitvoer

Yes No>

Tijdcomplexiteit : O(n) voor het maken van n sets met afzonderlijke items . Door de twee technieken: padcompressie met de unie op rang/grootte, zal de tijdscomplexiteit een vrijwel constante tijd bereiken. Het blijkt dat de finale afgeschreven tijdscomplexiteit is O(α(n)), waarbij α(n) de inverse Ackermann-functie is, die zeer gestaag groeit (deze bedraagt niet eens meer dan voor n<10⁶⁰⁰ongeveer).

Ruimtecomplexiteit: O(n) omdat we n elementen moeten opslaan in de Disjoint Set Data Structure.

Wat is een disjuncte verzameling datastructuur?

Ontdek of x en y tot dezelfde groep behoren of niet, d.w.z. of x en y directe/indirecte vrienden zijn.

Gebruikte datastructuren zijn:

Bewerkingen op disjuncte set-datastructuren:

1. Zoek:

C++

Java

Python3

C#

Javascript

2. Unie:

C++

Java

Python3

C#

Javascript

Optimalisaties (vereniging op rang/grootte en padcompressie):

Padcompressie (Aanpassingen aan Find()):

C++

Java

Python3

C#

Javascript

Unie op rang :

C++

Java

Python3

C#

Javascript

Unie op maat:

C++

Java

Python3

C#

Javascript

Hieronder vindt u de volledige implementatie van een disjuncte set met padcompressie en unie op rang.

C++

Java

Python3

C#

Javascript