INTRODUKTION TIL DISJOINT SÆT (UNION-FIND ALGORITHM)

Hvad er en disjoint sæt datastruktur?

To sæt kaldes usammenhængende sæt hvis de ikke har noget element til fælles, er skæringspunktet mellem sæt et nulsæt.

En datastruktur, der gemmer ikke-overlappende eller usammenhængende delmængde af elementer, kaldes usammenhængende datastruktur. Den usammenhængende datastruktur understøtter følgende operationer:

Tilføjelse af nye sæt til det usammenhængende sæt.
Sammenfletning af usammenhængende sæt til et enkelt usammenhængende sæt vha Union operation.
At finde repræsentant for et usammenhængende sæt ved hjælp af Find operation.
Tjek, om to sæt er usammenhængende eller ej.

Overvej en situation med et antal personer og følgende opgaver, der skal udføres på dem:

Tilføj en nyt venskab forhold , dvs. en person x bliver en anden persons ven, dvs. tilføjer nyt element til et sæt.
Find om individuelle x er en ven af individ y (direkte eller indirekte ven)

Eksempler:

Vi får 10 personer siger, a, b, c, d, e, f, g, h, i, j

Følgende er relationer, der skal tilføjes:
a b
b d
c f
c i
j e
g j

Givet forespørgsler som om a er en ven af d eller ej. Vi skal grundlæggende oprette følgende 4 grupper og opretholde en hurtig tilgængelig forbindelse mellem gruppeelementer:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e,g,j}
G4 = {h}

Find om x og y tilhører samme gruppe eller ej, dvs. for at finde ud af om x og y er direkte/indirekte venner.

Opdeling af individerne i forskellige sæt i henhold til de grupper, de falder i. Denne metode er kendt som en Usammenhængende sæt Union som vedligeholder en samling af Usammenhængende sæt og hvert sæt er repræsenteret af et af dets medlemmer.

For at besvare ovenstående spørgsmål er to nøglepunkter, der skal overvejes:

Hvordan løser man sæt? Til at begynde med hører alle elementer til forskellige sæt. Efter at have arbejdet med de givne relationer udvælger vi et medlem som en repræsentant . Der kan være mange måder at vælge en repræsentant på, en enkel er at vælge med det største indeks.
Tjek om 2 personer er i samme gruppe? Hvis repræsentanter for to personer er ens, bliver de venner.

De anvendte datastrukturer er:

Array: En matrix af heltal kaldes Forælder[] . Hvis vi har med at gøre N elementer, repræsenterer i'te element i arrayet det i'te element. Mere præcist er det i’te element i det overordnede[] array forælderen til det i’te element. Disse relationer skaber et eller flere virtuelle træer.

Træ: Det er en Usammenhængende sæt . Hvis to elementer er i samme træ, så er de i det samme Usammenhængende sæt . Rodknuden (eller den øverste knude) i hvert træ kaldes repræsentant af sættet. Der er altid en enkelt unik repræsentant af hvert sæt. En simpel regel til at identificere en repræsentant er, hvis 'i' er repræsentanten for et sæt, så Forælder[i] = i . Hvis jeg ikke er repræsentanten for hans sæt, så kan den findes ved at rejse op i træet, indtil vi finder repræsentanten.

Operationer på usammenhængende sæt datastrukturer:

Find
Union

1. Find:

Kan implementeres ved rekursivt at krydse det overordnede array, indtil vi rammer en node, der er forælderen til sig selv.

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

Tidskompleksitet : Denne tilgang er ineffektiv og kan i værste fald tage O(n) tid.

2. Union:

Det tager to elementer som input og finder repræsentanterne for deres sæt ved hjælp af Find operation, og til sidst sætter et af træerne (der repræsenterer sættet) under rodknudepunktet på det andet træ.

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

Tidskompleksitet : Denne tilgang er ineffektiv og kan i værste fald føre til træ med længden O(n).

Optimeringer (sammenslutning efter rang/størrelse og stikomprimering):

Effektiviteten afhænger meget af, hvilket træ der bliver knyttet til det andet . Der er 2 måder, hvorpå det kan gøres. Først er Union by Rank, som betragter højden af træet som faktoren, og anden er Union by Size, som betragter størrelsen af træet som faktoren, mens det ene træ fastgøres til det andet. Denne metode sammen med Path Compression giver kompleksitet på næsten konstant tid.

Path Kompression (Ændringer til Find()):

Det fremskynder datastrukturen med komprimering af højden af træerne. Det kan opnås ved at indsætte en lille caching-mekanisme i Find operation. Tag et kig på koden for flere detaljer:

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#

klasse vs objekt java

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

Tidskompleksitet : O(log n) i gennemsnit pr. opkald.

Union efter Rang :

Først og fremmest har vi brug for et nyt array af heltal kaldet rang[] . Størrelsen af dette array er den samme som det overordnede array Forælder[] . Hvis jeg er repræsentant for et sæt, rang[i] er højden af træet, der repræsenterer sættet.
Husk nu, at i Union-operationen er det ligegyldigt, hvilket af de to træer, der flyttes under det andet. Det, vi nu vil gøre, er at minimere højden af det resulterende træ. Hvis vi forener to træer (eller sæt), lad os kalde dem venstre og højre, så afhænger det hele af rang af venstre og rang af ret .

Hvis rang af venstre er mindre end rangen af højre , så er det bedst at flytte venstre under højre , fordi det ikke ændrer rangen af højre (mens flytning til højre under venstre ville øge højden). På samme måde, hvis rang af højre er mindre end rang af venstre, så skal vi flytte højre under venstre.
Hvis rækkerne er lige store, er det lige meget, hvilket træ der går under det andet, men resultatets rang vil altid være én større end træernes rangering.

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

Union efter størrelse:

Igen har vi brug for et nyt array af heltal kaldet størrelse[] . Størrelsen af dette array er den samme som det overordnede array Forælder[] . Hvis jeg er en repræsentant for et sæt, størrelse[i] er antallet af elementer i træet, der repræsenterer sættet.
Nu forener vi to træer (eller sæt), lad os kalde dem venstre og højre, så i dette tilfælde afhænger det hele af størrelse på venstre og størrelse på højre træ (eller sæt).

Hvis størrelsen på venstre er mindre end størrelsen på højre , så er det bedst at flytte venstre under højre og øge størrelsen på højre med størrelse på venstre. På samme måde, hvis størrelsen på højre er mindre end størrelsen på venstre, skal vi flytte til højre under venstre. og øge størrelsen på venstre med størrelsen på højre.
Hvis størrelserne er lige store, er det lige meget, hvilket træ der går under det andet.

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

Produktion

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

Tidskompleksitet : O(log n) uden Path Compression.

Nedenfor er den komplette implementering af disjoint sæt med stikomprimering og forening efter 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]) { parent[yset] = xset;   } // Hvis rækkerne er ens, så øg // rang.   else { parent[yset] = xset;   rang[xsæt] = rang[xsæt] + 1;   } } };    // Driver Code int main() { // Function Call DisjSet obj(5);   obj.Union(0, 2);   obj.Union(4, 2);   obj.Union(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'>);> }>

Produktion

Yes No>

Tidskompleksitet : O(n) til oprettelse af n enkelt varesæt. De to teknikker - sti komprimering med foreningen efter rang/størrelse, vil tidskompleksiteten nå næsten konstant tid. Det viser sig, at finalen amortiseret tidskompleksitet er O(α(n)), hvor α(n) er den omvendte Ackermann-funktion, som vokser meget støt (den overstiger ikke engang for n<10⁶⁰⁰rundt regnet).

Rumkompleksitet: O(n), fordi vi skal gemme n elementer i Disjoint Set Data Structure.

Hvad er en disjoint sæt datastruktur?

Find om x og y tilhører samme gruppe eller ej, dvs. for at finde ud af om x og y er direkte/indirekte venner.

De anvendte datastrukturer er:

Operationer på usammenhængende sæt datastrukturer:

1. Find:

C++

Java

Python3

C#

Javascript

2. Union:

C++

Java

Python3

C#

Javascript

Optimeringer (sammenslutning efter rang/størrelse og stikomprimering):

Path Kompression (Ændringer til Find()):

C++

Java

Python3

C#

Javascript

Union efter Rang :

C++

Java

Python3

C#

Javascript

Union efter størrelse:

C++

Java

Python3

C#

Javascript

Nedenfor er den komplette implementering af disjoint sæt med stikomprimering og forening efter rang.

C++

Java

Python3

C#

Javascript