Kas yra nevienodo rinkinio duomenų struktūra?
Vadinami du rinkiniai nesusiję rinkiniai jei jie neturi jokio bendro elemento, aibių sankirta yra nulinė aibė.
Duomenų struktūra, kurioje saugomi nepersidengiantys arba atskirti elementų poaibiai, vadinama nesujungta rinkinio duomenų struktūra. Nesujungta rinkinio duomenų struktūra palaiko šias operacijas:
- Naujų rinkinių įtraukimas į nesujungtą rinkinį.
- Nesujungtų rinkinių sujungimas į vieną nesujungtų rinkinį naudojant sąjunga operacija.
- Nesujungtos aibės atstovo radimas naudojant Rasti operacija.
- Patikrinkite, ar du rinkiniai yra atskirti, ar ne.
Apsvarstykite situaciją su keliais žmonėmis ir tokias užduotis, kurias jiems reikia atlikti:
- Pridėti nauja draugystė santykį , t.y. asmuo x tampa kito asmens y draugu, t. y. į aibę įtraukiamas naujas elementas.
- Sužinokite, ar individualus x yra asmens y draugas (tiesioginis ar netiesioginis draugas)
Pavyzdžiai:
Mums duota 10 asmenų, tarkim: a, b, c, d, e, f, g, h, i, j
Toliau pateikiami ryšiai, kuriuos reikia pridėti:
a b
b d
c f
c i
j e
g jPateiktos užklausos, pvz., ar a yra d draugas, ar ne. Iš esmės turime sukurti šias 4 grupes ir palaikyti greitai pasiekiamą ryšį tarp grupės elementų:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e,g,j}
G4 = {h}
Raskite, ar x ir y priklauso tai pačiai grupei, ar ne, t. y. sužinoti, ar x ir y yra tiesioginiai/netiesioginiai draugai.
Asmenų padalijimas į skirtingas aibes pagal grupes, į kurias jie patenka. Šis metodas žinomas kaip a Nesusijungęs rinkinys Sąjunga kuri tvarko kolekciją Nesusiję rinkiniai ir kiekvienam rinkiniui atstovauja vienas iš jos narių.
Norint atsakyti į aukščiau pateiktą klausimą, reikia atsižvelgti į du pagrindinius dalykus:
- Kaip išspręsti rinkinius? Iš pradžių visi elementai priklauso skirtingiems rinkiniams. Padirbę su duotais santykiais, pasirenkame narį kaip a atstovas . Atstovą galima pasirinkti įvairiais būdais, paprastas – pasirinkti su didžiausiu indeksu.
- Patikrinkite, ar 2 asmenys yra toje pačioje grupėje? Jei dviejų asmenų atstovai yra vienodi, jie taps draugais.
Naudojamos šios duomenų struktūros:
Masyvas: Vadinamas sveikųjų skaičių masyvas Tėvas[] . Jei turime reikalų su N elementai, i-asis masyvo elementas reiškia i-ąjį elementą. Tiksliau, Parent[] masyvo i’-asis elementas yra i’-ojo elemento pirminis elementas. Šie ryšiai sukuria vieną ar daugiau virtualių medžių.
Medis: Tai yra Nesusijungęs rinkinys . Jei du elementai yra tame pačiame medyje, tada jie yra tame pačiame Nesusijungęs rinkinys . Kiekvieno medžio šaknies mazgas (arba aukščiausias mazgas) vadinamas atstovas rinkinio. Visada yra vienas unikalus atstovas kiekvieno rinkinio. Paprasta atstovo identifikavimo taisyklė yra tokia: jei „i“ yra rinkinio atstovas, tada Tėvas [i] = i . Jei aš nesu jo rinkinio atstovas, tai jį galima rasti keliaudamas į medį, kol rasime atstovą.
Operacijos su nevienodomis rinkinių duomenų struktūromis:
- Rasti
- sąjunga
1. Rasti:
Galima įgyvendinti rekursyviai kertant pirminį masyvą, kol nepasieksime mazgo, kuris yra pats pirminis.
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> > |
>
>
Laiko sudėtingumas : Šis metodas yra neefektyvus ir blogiausiu atveju gali užtrukti O (n) laiko.
2. Sąjunga:
Užtrunka du elementai kaip įvestį ir suranda jų aibių atstovus naudodamas Rasti operaciją ir galiausiai vieną iš medžių (atstovaujančių rinkiniui) įdeda po kito medžio šaknies mazgu.
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;> }> |
>
>
Laiko sudėtingumas : Šis metodas yra neefektyvus ir blogiausiu atveju gali sukelti O(n) ilgio medį.
Optimizavimas (sujungimas pagal reitingą / dydį ir kelio suspaudimą):
Efektyvumas labai priklauso nuo to, kuris medis prisiriša prie kito . Yra 2 būdai, kaip tai padaryti. Pirma, sujungimas pagal rangą, kuris laiko veiksniu medžio aukštį, o antrasis yra jungtis pagal dydį, kuris atsižvelgia į medžio dydį kaip veiksnį, jungiant vieną medį prie kito. Šis metodas kartu su Path Compression suteikia beveik pastovaus laiko sudėtingumą.
Kelio suspaudimas (Find() modifikacijos):
Tai pagreitina duomenų struktūrą suspaudžiant aukštį iš medžių. Tai galima pasiekti įterpiant nedidelį talpyklos mechanizmą Rasti operacija. Norėdami gauti daugiau informacijos, pažiūrėkite į kodą:
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#
atgalinio skambučio pragaras javascript
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.> |
>
>
Laiko sudėtingumas : O(log n) vidutiniškai vienam skambučiui.
Sąjunga pagal rangą :
Visų pirma, mums reikia naujo sveikųjų skaičių masyvo, vadinamo rangas[] . Šio masyvo dydis yra toks pat kaip pirminio masyvo Tėvas[] . Jei esu rinkinio atstovas, rangas[i] yra aibę reprezentuojančio medžio aukštis.
Dabar prisiminkite, kad Sąjungos operacijoje nesvarbu, kuris iš dviejų medžių perkeliamas po kitu. Dabar mes norime sumažinti gauto medžio aukštį. Jei sujungiame du medžius (arba rinkinius), vadinkime juos kairiuoju ir dešiniuoju, tada viskas priklauso nuo kairiųjų rangas ir teisingumo rangas .
- Jei rangas paliko yra mažesnis už rangą teisingai , tada geriausia judėti kairė po dešine , nes tai nepakeis dešiniojo rango (o judant dešinėn po kairiuoju aukštis padidėtų). Lygiai taip pat, jei dešiniojo rangas yra mažesnis nei kairiojo, tada turėtume pereiti į dešinę po kairiuoju.
- Jei rangai yra vienodi, nesvarbu, kuris medis patenka po kitu, tačiau rezultato rangas visada bus vienu didesnis nei medžių rangas.
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 }> |
>
>
Sąjunga pagal dydį:
Vėlgi, mums reikia naujo sveikųjų skaičių masyvo, vadinamo dydis[] . Šio masyvo dydis yra toks pat kaip pirminio masyvo Tėvas[] . Jei esu rinkinio atstovas, dydis [i] yra aibę vaizduojančio medžio elementų skaičius.
Dabar mes sujungiame du medžius (arba rinkinius), pavadinkime juos kaire ir dešine, tada šiuo atveju viskas priklauso nuo kairiojo dydžio ir dešinės dydis medis (arba rinkinys).
- Jei dydis paliko yra mažesnis nei dydis teisingai , tada geriausia judėti kairė po dešine ir padidinkite dešinės pusės dydį kairiosios. Lygiai taip pat, jei dešinės dydis yra mažesnis už kairiojo dydį, tada turėtume judėti dešinėn po kairiuoju. ir padidinkite kairiosios dydį dešinės dydžiu.
- Jei dydžiai vienodi, nesvarbu, kuris medis eina po kitu.
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]++; } } }> |
>
>Išvestis
Element 0: Representative = 0 Element 1: Representative = 0 Element 2: Representative = 2 Element 3: Representative = 2 Element 4: Representative = 0>
Laiko sudėtingumas : O(log n) be kelio suspaudimo.
Toliau pateikiamas visas disjunktinio rinkinio įgyvendinimas su kelio suspaudimu ir sujungimu pagal 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;>> >}> > >// 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]>rangas[yset]) { parent[yset] = xset; } // Jei rangai yra vienodi, tada padidinkite // rangą. else { tėvas[yset] = xset; rangas[xset] = rangas[xset] + 1; } } }; // Vairuotojo kodas int main() { // Funkcijos iškvietimas DisjSet obj(5); obj.Sąjunga(0, 2); obj.Sąjunga(4, 2); obj.Sąjunga(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>.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>.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'>);> }> |
>
>Išvestis
Yes No>
Laiko sudėtingumas : O(n) n atskirų elementų rinkinių kūrimui . Dvi būdai – kelio suspaudimas su sąjunga pagal rangą/dydį, laiko sudėtingumas pasieks beveik pastovų laiką. Pasirodo, kad finalas amortizuotas laiko sudėtingumas yra O(α(n)), kur α(n) yra atvirkštinė Akermano funkcija, kuri auga labai stabiliai (net neviršija, kai n<10600maždaug).
Erdvės sudėtingumas: O(n), nes turime saugoti n elementų nevienodo rinkinio duomenų struktūroje.