Mikä on Disjoint-joukkotietorakenne?
Kaksi sarjaa kutsutaan hajanaisia joukkoja jos niillä ei ole mitään yhteistä elementtiä, joukkojen leikkauspiste on nollajoukko.
Tietorakennetta, joka tallentaa ei-päällekkäisiä tai erillisiä elementtien osajoukkoja, kutsutaan disjoint-joukkotietorakenteeksi. Disjunkt-joukkotietorakenne tukee seuraavia toimintoja:
- Uusien sarjojen lisääminen epäyhtenäiseen joukkoon.
- Disjunktijoukkojen yhdistäminen yhdeksi disjunktijoukoksi käyttämällä liitto operaatio.
- Disjunktijoukon edustajan löytäminen käyttämällä löytö operaatio.
- Tarkista, ovatko kaksi sarjaa erillään vai eivät.
Harkitse tilannetta, jossa on useita henkilöitä, ja seuraavia tehtäviä, jotka on suoritettava heille:
- Lisää uusi ystävyys suhde , eli henkilö x tulee toisen henkilön y ystävä eli lisää uuden elementin joukkoon.
- Selvitä onko yksilö x on yksilön y ystävä (suora tai välillinen ystävä)
Esimerkkejä:
Meille annetaan 10 yksilöä sanovat, a, b, c, d, e, f, g, h, i, j
Seuraavat suhteet lisätään:
a b
b d
c f
c i
j e
g jAnnetut kyselyt, kuten onko a d:n ystävä vai ei. Meidän on periaatteessa luotava seuraavat 4 ryhmää ja ylläpidettävä nopeasti saatavilla olevaa yhteyttä ryhmän kohteiden välillä:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e,g,j}
G4 = {h}
Selvitä, kuuluvatko x ja y samaan ryhmään vai eivät, eli ovatko x ja y suoria/epäsuoria ystäviä.
Yksilöt jaetaan eri ryhmiin sen mukaan, mihin ryhmiin he kuuluvat. Tämä menetelmä tunnetaan nimellä a Erillinen joukko Unioni joka ylläpitää kokoelmaa Hajanaiset sarjat ja jokaista sarjaa edustaa yksi sen jäsenistä.
Yllä olevaan kysymykseen vastaamiseksi on otettava huomioon kaksi keskeistä asiaa:
- Kuinka ratkaista sarjat? Aluksi kaikki elementit kuuluvat eri ryhmiin. Kun olet työskennellyt annettujen suhteiden parissa, valitsemme jäseneksi a edustaja . Edustajan valitsemiseen voi olla monia tapoja, yksinkertainen tapa on valita suurimmalla indeksillä.
- Tarkista, onko 2 henkilöä samassa ryhmässä? Jos kahden henkilön edustajat ovat samat, heistä tulee ystäviä.
Käytetyt tietorakenteet ovat:
Taulukko: Kutsutaan kokonaislukujen joukkoa Vanhempi[] . Jos olemme tekemisissä N kohteita, taulukon i:s elementti edustaa i:ttä alkiota. Tarkemmin sanottuna Parent[]-taulukon i'th-elementti on i:nnen alkion yläelementti. Nämä suhteet luovat yhden tai useamman virtuaalisen puun.
Puu: Se on a Hajanainen setti . Jos kaksi elementtiä ovat samassa puussa, ne ovat samassa Hajanainen setti . Kunkin puun juurisolmua (tai ylintä solmua) kutsutaan nimellä edustaja sarjasta. Aina löytyy yksittäinen ainutlaatuinen edustaja jokaisesta setistä. Yksinkertainen sääntö edustajan tunnistamiseksi on, jos 'i' on joukon edustaja, silloin Vanhempi[i] = i . Jos en ole hänen joukkonsa edustaja, niin se löytyy matkustamalla ylös puuhun, kunnes löydämme edustajan.
Toiminnot erillisten joukkotietorakenteiden kanssa:
- löytö
- liitto
1. Etsi:
Voidaan toteuttaa kiertämällä rekursiivisesti ylätason taulukon läpi, kunnes osumme solmuun, joka on itsensä vanhempi.
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> |
>
>
Python 3
# 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> > |
>
>
Aika monimutkaisuus : Tämä lähestymistapa on tehoton ja voi kestää O(n) aikaa pahimmassa tapauksessa.
2. Unioni:
Se ottaa kaksi elementtiä syötteenä ja etsii joukkojensa edustajat käyttämällä löytö ja lopulta asettaa jommankumman puun (joukkoa edustavan) toisen puun juurisolmun alle.
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); } }> |
>
>
Python 3
# 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;> }> |
>
>
Aika monimutkaisuus : Tämä lähestymistapa on tehoton ja voi pahimmassa tapauksessa johtaa puuhun, jonka pituus on O(n).
Optimoinnit (Yhdistys sijoituksen/koon ja polun pakkauksen mukaan):
Tehokkuus riippuu suuresti siitä, mikä puu kiinnittyy toiseen . On 2 tapaa, joilla se voidaan tehdä. Ensimmäinen on Union by Rank, joka pitää puun korkeutta tekijänä ja toinen on Union by Size, joka ottaa puun koon tekijänä samalla kun puu liitetään toiseen. Tämä menetelmä yhdessä Path Compression kanssa antaa lähes vakioajan monimutkaisuuden.
Polun pakkaus (Muokkaukset Find()-kohtaan):
Se nopeuttaa tietorakennetta mm korkeuden puristamista puista. Se voidaan saavuttaa lisäämällä pieni välimuistimekanismi löytö operaatio. Katso lisätietoja koodista:
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.> |
>
>
Python 3
# 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#
fizzbuzz 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.> |
>
>
Aika monimutkaisuus : O(log n) keskimäärin per puhelu.
Liitto sijoituksen mukaan :
Ensinnäkin tarvitsemme uuden kokonaislukujoukon nimeltä sijoitus[] . Tämän taulukon koko on sama kuin päätaulukon koko Vanhempi[] . Jos olen joukon edustaja, sijoitus[i] on joukkoa edustavan puun korkeus.
Muista nyt, että Union-operaatiossa ei ole väliä kumpi kahdesta puusta siirretään toisen alle. Nyt haluamme minimoida tuloksena olevan puun korkeuden. Jos yhdistämme kaksi puuta (tai joukkoa), kutsutaan niitä vasemmalle ja oikealle, niin kaikki riippuu arvo vasemmisto ja oikeuden arvo .
- Jos sijoitus vasemmalle on pienempi kuin arvo oikein , silloin on parasta liikkua vasen oikean alla , koska se ei muuta oikeiston sijoitusta (vaikka oikealle siirtäminen vasemman alle lisäisi korkeutta). Samalla tavalla, jos oikeiston arvo on pienempi kuin vasemman, meidän pitäisi siirtyä oikealle vasemman alle.
- Jos arvot ovat yhtä suuret, ei ole väliä mikä puu menee toisen alle, mutta tuloksen arvo on aina yhtä suurempi kuin puiden arvo.
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)); } } }> |
>
>
Python 3
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 }> |
>
>
Liitto koon mukaan:
Jälleen tarvitsemme uuden kokonaislukujoukon nimeltä koko[] . Tämän taulukon koko on sama kuin päätaulukon koko Vanhempi[] . Jos olen joukon edustaja, koko [i] on joukkoa edustavien puun elementtien lukumäärä.
Nyt yhdistämme kaksi puuta (tai joukkoa), kutsutaan niitä vasemmaksi ja oikeaksi, niin tässä tapauksessa kaikki riippuu vasemman kokoinen ja oikean kokoinen puu (tai sarja).
- Jos koko vasemmalle on pienempi kuin koko oikein , silloin on parasta liikkua vasen oikean alla ja suurenna oikean kokoa vasemman koolla. Samalla tavalla, jos oikean koko on pienempi kuin vasemman koko, meidän tulisi siirtyä oikealle vasemman alle. ja suurenna vasemman kokoa oikean koolla.
- Jos koot ovat samat, ei ole väliä mikä puu menee toisen alle.
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> |
>
>
Python 3
# 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]++; } } }> |
>
>Lähtö
Element 0: Representative = 0 Element 1: Representative = 0 Element 2: Representative = 2 Element 3: Representative = 2 Element 4: Representative = 0>
Aika monimutkaisuus : O(log n) ilman polun pakkausta.
Alla on disjunkt-joukon täydellinen toteutus polun pakkauksella ja liitännällä arvon mukaan.
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]>sijoitus[yset]) { vanhempi[yset] = xset; } // Jos arvot ovat samat, lisää // arvoa. else { vanhempi[yset] = xset; sijoitus[xset] = sijoitus[xset] + 1; } } }; // Ohjainkoodi int main() { // Toimintokutsu 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'); } }> |
>
>
Python 3
# 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'>);> }> |
>
>Lähtö
Yes No>
Aika monimutkaisuus : O(n) n yksittäisen alkiosarjan luomiseen. Kaksi tekniikkaa - polkupakkaus liiton kanssa arvon/koon mukaan, aika monimutkaisuus saavuttaa lähes vakioajan. Kävi ilmi, että finaali kuoletettu aika monimutkaisuus on O(α(n)), missä α(n) on käänteinen Ackermann-funktio, joka kasvaa erittäin tasaisesti (se ei ylitä edes n<10600suunnilleen).
Avaruuden monimutkaisuus: O(n), koska meidän on tallennettava n elementtiä Disjoint Set Data Structureen.