UVOD V DISJUNKTNO MNOŽICO (ALGORITEM ISKANJA UNIJE) - TECHCODEVIEW.COM

Kaj je podatkovna struktura nepovezanega niza?

Pokličeta dva sklopa disjunktne množice če nimata nobenega skupnega elementa, je presečišče množic ničelna množica.

Podatkovna struktura, ki hrani neprekrivajočo se ali ločeno podmnožico elementov, se imenuje podatkovna struktura nepovezanega niza. Podatkovna struktura ločenega niza podpira naslednje operacije:

Dodajanje novih množic disjunktni množici.
Spajanje disjunktnih množic v eno samo disjunktno množico z uporabo zveza delovanje.
Iskanje predstavnika disjunktne množice z uporabo Najti delovanje.
Preverite, ali sta dve množici disjunktni ali ne.

Razmislite o situaciji s številnimi osebami in naslednjimi nalogami, ki jih je treba opraviti:

Dodaj a novo prijateljstvo odnos , tj. oseba x postane prijatelj druge osebe y, tj. dodajanje novega elementa v niz.
Ugotovite, ali posameznik x je prijatelj posameznika y (neposredni ali posredni prijatelj)

Primeri:

Danih nam je 10 posameznikov, recimo a, b, c, d, e, f, g, h, i, j

Dodati je treba naslednje odnose:
a b
b d
c f
c i
j e
g j

Glede na poizvedbe, kot je, ali je a prijatelj osebe d ali ne. V bistvu moramo ustvariti naslednje 4 skupine in vzdrževati hitro dostopno povezavo med elementi skupine:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e,g,j}
G4 = {h}

Ugotovite, ali x in y pripadata isti skupini ali ne, tj. ugotovite, ali sta x in y neposredna/posredna prijatelja.

Razdelitev posameznikov v različne sklope glede na skupine, v katere spadajo. Ta metoda je znana kot a Disjunktna množica Unija ki vzdržuje zbirko Disjunktne množice in vsak niz je predstavljen z enim od njegovih članov.

Za odgovor na zgornje vprašanje je treba upoštevati dve ključni točki:

Kako razrešiti sklope? Na začetku vsi elementi pripadajo različnim množicam. Po obdelavi danih relacij izberemo člana kot a predstavnik . Predstavnika je mogoče izbrati na več načinov, preprost je izbor z največjim indeksom.
Preverite, ali sta 2 osebi v isti skupini? Če sta predstavnika dveh posameznikov enaka, bosta postala prijatelja.

Uporabljene podatkovne strukture so:

niz: Pokliče se niz celih števil starš[] . Če imamo opravka s n elementov, i-ti element matrike predstavlja i-ti element. Natančneje, i-ti element matrike Parent[] je nadrejeni element i-tega elementa. Ta razmerja ustvarijo eno ali več virtualnih dreves.

Drevo: Je Disjunktna množica . Če sta dva elementa v istem drevesu, potem sta v istem Disjunktna množica . Korensko vozlišče (ali najvišje vozlišče) vsakega drevesa se imenuje predstavnik kompleta. Vedno je en sam edinstven predstavnik vsakega niza. Preprosto pravilo za identifikacijo predstavnika je, če je 'i' predstavnik množice Starš[i] = i . Če i ni predstavnik njegove množice, ga lahko najdemo tako, da potujemo po drevesu, dokler ne najdemo predstavnika.

Operacije na podatkovnih strukturah nepovezanega niza:

Najti
zveza

1. Poiščite:

Lahko se izvede z rekurzivnim prečkanjem nadrejenega polja, dokler ne zadenemo vozlišča, ki je nadrejeno samo sebi.

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

Časovna zapletenost : Ta pristop je neučinkovit in lahko v najslabšem primeru traja O(n) časa.

2. Zveza:

Vzame dva elementa kot vhod in najde predstavnike svojih množic z uporabo Najti operacijo in končno eno od dreves (ki predstavlja množico) postavi pod korensko vozlišče drugega drevesa.

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

Časovna zapletenost : Ta pristop je neučinkovit in lahko v najslabšem primeru vodi do drevesa dolžine O(n).

Optimizacije (združevanje glede na rang/velikost in stiskanje poti):

Učinkovitost je močno odvisna od tega, katero drevo se pritrdi na drugega . To lahko storite na dva načina. Prvi je Union by Rank, ki upošteva višino drevesa kot dejavnik, drugi pa je Union by Size, ki upošteva velikost drevesa kot dejavnik pri pritrjevanju enega drevesa na drugega. Ta metoda skupaj s kompresijo poti daje kompleksnost skoraj konstantnega časa.

Stiskanje poti (Spremembe funkcije Find()):

Pospeši strukturo podatkov za stiskanje višine od dreves. To lahko dosežete tako, da vstavite majhen mehanizem za predpomnjenje Najti delovanje. Za več podrobnosti si oglejte kodo:

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#

pojasni neodvisnost podatkov

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

Časovna zapletenost : O(log n) v povprečju na klic.

Zveza po rangu :

Najprej potrebujemo novo matriko celih števil, imenovano uvrstitev [] . Velikost te matrike je enaka velikosti nadrejene matrike starš[] . Če je i predstavnik množice, uvrstitev[i] je višina drevesa, ki predstavlja niz.
Zdaj pa se spomnimo, da v operaciji Union ni pomembno, katero od obeh dreves je premaknjeno pod drugega. Zdaj pa želimo minimizirati višino nastalega drevesa. Če združujemo dve drevesi (ali množici), recimo jima levo in desno, potem je vse odvisno od rang leve in rang pravice .

Če je rang levo je nižji od ranga prav , potem je najbolje, da se premaknete levo pod desno , ker to ne bo spremenilo ranga desne (medtem ko bi premikanje desne pod levo povečalo višino). Na enak način, če je položaj desne nižji od položaja levice, se moramo premakniti desno pod levo.
Če so rangi enaki, ni pomembno, katero drevo je pod drugim, vendar bo rang rezultata vedno višji od ranga dreves.

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

Zveza po velikosti:

Spet potrebujemo novo matriko celih števil, imenovano velikost[] . Velikost te matrike je enaka velikosti nadrejene matrike starš[] . Če sem predstavnik niza, velikost [i] je število elementov v drevesu, ki predstavlja množico.
Zdaj združujemo dve drevesi (ali množici), recimo jima levo in desno, potem je v tem primeru vse odvisno od velikost leve in velikost desne drevo (ali komplet).

Če je velikost levo je manjša od velikosti prav , potem je najbolje, da se premaknete levo pod desno in povečajte velikost desne za velikost leve. Na enak način, če je velikost desne manjša od velikosti leve, potem se moramo premakniti desno pod levo. in povečajte velikost leve za velikost desne.
Če sta velikosti enaki, ni pomembno, katero drevo gre pod drugo.

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

Izhod

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

Časovna zapletenost : O(log n) brez stiskanja poti.

Spodaj je popolna izvedba disjunktne množice s stiskanjem poti in združevanjem po rangu.

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]>rank[yset]) { parent[yset] = xset;   } // Če so rangi enaki, potem povečaj // rang.   else { parent[yset] = xset;   rang[xset] = rang[xset] + 1;   } } };    // Koda gonilnika int main() { // Klic funkcije DisjSet obj(5);   obj.Unija(0, 2);   obj.Unija(4, 2);   obj.Unija(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'>);> }>

Izhod

Yes No>

Časovna zapletenost : O(n) za ustvarjanje n kompletov posameznih postavk. Dve tehniki - stiskanje poti z združitvijo po rangu/velikosti bo časovna kompleksnost dosegla skoraj konstanten čas. Izkazalo se je, da končni amortizirana časovna kompleksnost je O(α(n)), kjer je α(n) inverzna Ackermannova funkcija, ki zelo enakomerno raste (ne preseže niti pri n<10⁶⁰⁰približno).

Kompleksnost prostora: O(n), ker moramo shraniti n elementov v podatkovni strukturi nepovezanega niza.

Uvod v disjunktno množico (algoritem za iskanje združevanja)

Kaj je podatkovna struktura nepovezanega niza?

Ugotovite, ali x in y pripadata isti skupini ali ne, tj. ugotovite, ali sta x in y neposredna/posredna prijatelja.

Uporabljene podatkovne strukture so:

Operacije na podatkovnih strukturah nepovezanega niza:

1. Poiščite:

C++

Java

Python3

C#

Javascript

2. Zveza:

C++

Java

Python3

C#

Javascript

Optimizacije (združevanje glede na rang/velikost in stiskanje poti):

Stiskanje poti (Spremembe funkcije Find()):

C++

Java

Python3

C#

Javascript

Zveza po rangu :

C++

Java

Python3

C#

Javascript

Zveza po velikosti:

C++

Java

Python3

C#

Javascript

Spodaj je popolna izvedba disjunktne množice s stiskanjem poti in združevanjem po rangu.

C++

Java

Python3

C#

Javascript