Qu'est-ce qu'une structure de données d'ensemble disjoint ?
Deux ensembles sont appelés ensembles disjoints s’ils n’ont aucun élément en commun, l’intersection des ensembles est un ensemble nul.
Une structure de données qui stocke un sous-ensemble d’éléments non chevauchants ou disjoints est appelée structure de données d’ensemble disjoint. La structure de données d'ensemble disjoint prend en charge les opérations suivantes :
- Ajout de nouveaux ensembles à l'ensemble disjoint.
- Fusionner des ensembles disjoints en un seul ensemble disjoint à l'aide de syndicat opération.
- Trouver un représentant d'un ensemble disjoint en utilisant Trouver opération.
- Vérifiez si deux ensembles sont disjoints ou non.
Considérons une situation avec un certain nombre de personnes et les tâches suivantes doivent être exécutées sur elles :
- Ajouter un nouvelle amitié relation , c'est-à-dire qu'une personne x devient l'amie d'une autre personne y, c'est-à-dire qu'elle ajoute un nouvel élément à un ensemble.
- Déterminez si un individu x est un ami de l'individu y (ami direct ou indirect)
Exemples:
On nous donne 10 individus, disons, a, b, c, d, e, f, g, h, i, j
Voici les relations à ajouter :
un B
bd
cf
c je
je
gjÉtant donné des requêtes telles que si a est un ami de d ou non. Nous devons essentiellement créer les 4 groupes suivants et maintenir une connexion rapidement accessible entre les éléments du groupe :
G1 = {une, b, ré}
G2 = {c, f, je}
G3 = {e,g,j}
G4 = {h}
Déterminez si x et y appartiennent ou non au même groupe, c'est-à-dire si x et y sont des amis directs/indirects.
Partitionner les individus en différents ensembles selon les groupes dans lesquels ils appartiennent. Cette méthode est connue sous le nom de Union des ensembles disjoints qui conserve une collection de Ensembles disjoints et chaque ensemble est représenté par l'un de ses membres.
Pour répondre à la question ci-dessus, deux points clés à considérer sont :
- Comment résoudre des ensembles ? Initialement, tous les éléments appartiennent à des ensembles différents. Après avoir travaillé sur les relations données, nous sélectionnons un membre comme représentant . Il peut y avoir de nombreuses façons de sélectionner un représentant, la plus simple consiste à sélectionner avec l'indice le plus élevé.
- Vérifier si 2 personnes sont dans le même groupe ? Si les représentants de deux individus sont identiques, ils deviendront amis.
Les structures de données utilisées sont :
Tableau: Un tableau d’entiers s’appelle Parent[] . Si nous avons affaire à N items, le ième élément du tableau représente le ième élément. Plus précisément, le ième élément du tableau Parent[] est le parent du ième élément. Ces relations créent un ou plusieurs arbres virtuels.
Arbre: C'est un Ensemble disjoint . Si deux éléments sont dans le même arbre, alors ils sont dans le même Ensemble disjoint . Le nœud racine (ou le nœud le plus élevé) de chaque arbre est appelé le représentant de l'ensemble. Il y en a toujours un seul représentant unique de chaque ensemble. Une règle simple pour identifier un représentant est la suivante : si « i » est le représentant d’un ensemble, alors Parent[je] = je . Si je ne suis pas le représentant de son ensemble, alors il peut être trouvé en remontant l'arbre jusqu'à ce que nous trouvions le représentant.
Opérations sur les structures de données d'ensembles disjoints :
- Trouver
- syndicat
1. Recherchez :
Peut être implémenté en parcourant de manière récursive le tableau parent jusqu'à ce que nous atteignions un nœud qui est son parent.
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> > |
>
>
Complexité temporelle : Cette approche est inefficace et peut prendre un temps O(n) dans le pire des cas.
2. Syndicat :
Ça prend deux éléments comme entrée et trouve les représentants de leurs ensembles en utilisant le Trouver opération, et place finalement l'un ou l'autre des arbres (représentant l'ensemble) sous le nœud racine de l'autre arbre.
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;> }> |
>
>
Complexité temporelle : Cette approche est inefficace et pourrait conduire à un arbre de longueur O(n) dans le pire des cas.
Optimisations (Union par rang/taille et compression de chemin) :
L'efficacité dépend fortement de l'arbre attaché à l'autre. . Il existe 2 manières de procéder. Le premier est l'Union par rang, qui considère la hauteur de l'arbre comme facteur et le deuxième est l'Union par taille, qui considère la taille de l'arbre comme facteur tout en attachant un arbre à l'autre. Cette méthode, associée à la compression de chemin, donne une complexité en temps presque constant.
Compression du chemin (Modifications à rechercher()) :
Il accélère la structure des données en compresser la hauteur des arbres. Cela peut être réalisé en insérant un petit mécanisme de mise en cache dans le Trouver opération. Jetez un oeil au code pour plus de détails:
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#
python chameau
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.> |
>
>
Complexité temporelle : O(log n) en moyenne par appel.
Union par rang :
Tout d’abord, nous avons besoin d’un nouveau tableau d’entiers appelé rang[] . La taille de ce tableau est la même que celle du tableau parent Parent[] . Si je suis le représentant d'un ensemble, rang[i] est la hauteur de l'arbre représentant l'ensemble.
Rappelons maintenant que dans l’opération Union, peu importe lequel des deux arbres est déplacé sous l’autre. Maintenant, ce que nous voulons faire, c'est minimiser la hauteur de l'arbre résultant. Si nous réunissons deux arbres (ou ensembles), appelons-les gauche et droite, alors tout dépend de la grade de gauche et le rang de droit .
- Si le rang de gauche est inférieur au rang de droite , alors il vaut mieux déménager gauche sous droite , car cela ne changera pas le rang de la droite (alors que se déplacer vers la droite sous la gauche augmenterait la hauteur). De la même manière, si le rang de droite est inférieur à celui de gauche, alors on devrait passer de droite en dessous de gauche.
- Si les rangs sont égaux, peu importe quel arbre passe sous l’autre, mais le rang du résultat sera toujours supérieur d’un rang au rang des arbres.
C++
// Unites the set that includes i and the set> // that includes j by rank> > #include> using> namespace> std;> > void> unionbyrank(>int> i,>int> j) {> > >// Find the representatives (or the root nodes)> >// for the set that includes i> >int> irep =>this>.find(i);> > >// And do the same for the set that includes j> >int> jrep =>this>.Find(j);> > >// Elements are in same set, no need to> >// unite anything.> >if> (irep == jrep)> >return>;> > >// Get the rank of i’s tree> >irank = Rank[irep],> > >// Get the rank of j’s tree> >jrank = Rank[jrep];> > >// If i’s rank is less than j’s rank> >if> (irank // Then move i under j this.parent[irep] = jrep; } // Else if j’s rank is less than i’s rank else if (jrank // Then move j under i this.Parent[jrep] = irep; } // Else if their ranks are the same else { // Then move i under j (doesn’t matter // which one goes where) this.Parent[irep] = jrep; // And increment the result tree’s // rank by 1 Rank[jrep]++; } }> |
>
>
Java
public> class> DisjointSet {> > >private> int>[] parent;> >private> int>[] rank;> > >// Constructor to initialize the DisjointSet data> >// structure> >public> DisjointSet(>int> size)> >{> >parent =>new> int>[size];> >rank =>new> int>[size];> > >// Initialize each element as a separate set with> >// rank 0> >for> (>int> i =>0>; i parent[i] = i; rank[i] = 0; } } // Function to find the representative (or the root // node) of a set with path compression private int find(int i) { if (parent[i] != i) { parent[i] = find(parent[i]); // Path compression } return parent[i]; } // Unites the set that includes i and the set that // includes j by rank public void unionByRank(int i, int j) { // Find the representatives (or the root nodes) for // the set that includes i and j int irep = find(i); int jrep = find(j); // Elements are in the same set, no need to unite // anything if (irep == jrep) { return; } // Get the rank of i's tree int irank = rank[irep]; // Get the rank of j's tree int jrank = rank[jrep]; // If i's rank is less than j's rank if (irank // Move i under j parent[irep] = jrep; } // Else if j's rank is less than i's rank else if (jrank // Move j under i parent[jrep] = irep; } // Else if their ranks are the same else { // Move i under j (doesn't matter which one goes // where) parent[irep] = jrep; // Increment the result tree's rank by 1 rank[jrep]++; } } // Example usage public static void main(String[] args) { int size = 5; DisjointSet ds = new DisjointSet(size); // Perform some union operations ds.unionByRank(0, 1); ds.unionByRank(2, 3); ds.unionByRank(1, 3); // Find the representative of each element and print // the result for (int i = 0; i System.out.println( 'Element ' + i + ' belongs to the set with representative ' + ds.find(i)); } } }> |
>
>
Python3
class> DisjointSet:> >def> __init__(>self>, size):> >self>.parent>=> [i>for> i>in> range>(size)]> >self>.rank>=> [>0>]>*> size> > ># Function to find the representative (or the root node) of a set> >def> find(>self>, i):> ># If i is not the representative of its set, recursively find the representative> >if> self>.parent[i] !>=> i:> >self>.parent[i]>=> self>.find(>self>.parent[i])># Path compression> >return> self>.parent[i]> > ># Unites the set that includes i and the set that includes j by rank> >def> union_by_rank(>self>, i, j):> ># Find the representatives (or the root nodes) for the set that includes i and j> >irep>=> self>.find(i)> >jrep>=> self>.find(j)> > ># Elements are in the same set, no need to unite anything> >if> irep>=>=> jrep:> >return> > ># Get the rank of i's tree> >irank>=> self>.rank[irep]> > ># Get the rank of j's tree> >jrank>=> self>.rank[jrep]> > ># If i's rank is less than j's rank> >if> irank # Move i under j self.parent[irep] = jrep # Else if j's rank is less than i's rank elif jrank # Move j under i self.parent[jrep] = irep # Else if their ranks are the same else: # Move i under j (doesn't matter which one goes where) self.parent[irep] = jrep # Increment the result tree's rank by 1 self.rank[jrep] += 1 def main(self): # Example usage size = 5 ds = DisjointSet(size) # Perform some union operations ds.union_by_rank(0, 1) ds.union_by_rank(2, 3) ds.union_by_rank(1, 3) # Find the representative of each element for i in range(size): print(f'Element {i} belongs to the set with representative {ds.find(i)}') # Creating an instance and calling the main method ds = DisjointSet(size=5) ds.main()> |
>
>
C#
using> System;> > class> DisjointSet {> >private> int>[] parent;> >private> int>[] rank;> > >public> DisjointSet(>int> size) {> >parent =>new> int>[size];> >rank =>new> int>[size];> > >// Initialize each element as a separate set> >for> (>int> i = 0; i parent[i] = i; rank[i] = 0; } } // Function to find the representative (or the root node) of a set private int Find(int i) { // If i is not the representative of its set, recursively find the representative if (parent[i] != i) { parent[i] = Find(parent[i]); // Path compression } return parent[i]; } // Unites the set that includes i and the set that includes j by rank public void UnionByRank(int i, int j) { // Find the representatives (or the root nodes) for the set that includes i and j int irep = Find(i); int jrep = Find(j); // Elements are in the same set, no need to unite anything if (irep == jrep) { return; } // Get the rank of i's tree int irank = rank[irep]; // Get the rank of j's tree int jrank = rank[jrep]; // If i's rank is less than j's rank if (irank // Move i under j parent[irep] = jrep; } // Else if j's rank is less than i's rank else if (jrank // Move j under i parent[jrep] = irep; } // Else if their ranks are the same else { // Move i under j (doesn't matter which one goes where) parent[irep] = jrep; // Increment the result tree's rank by 1 rank[jrep]++; } } static void Main() { // Example usage int size = 5; DisjointSet ds = new DisjointSet(size); // Perform some union operations ds.UnionByRank(0, 1); ds.UnionByRank(2, 3); ds.UnionByRank(1, 3); // Find the representative of each element for (int i = 0; i Console.WriteLine('Element ' + i + ' belongs to the set with representative ' + ds.Find(i)); } } }> |
>
>
Javascript
// JavaScript Program for the above approach> unionbyrank(i, j) {> let irep =>this>.find(i);>// Find representative of set including i> let jrep =>this>.find(j);>// Find representative of set including j> > if> (irep === jrep) {> return>;>// Elements are already in the same set> }> > let irank =>this>.rank[irep];>// Rank of set including i> let jrank =>this>.rank[jrep];>// Rank of set including j> > if> (irank this.parent[irep] = jrep; // Make j's representative parent of i's representative } else if (jrank this.parent[jrep] = irep; // Make i's representative parent of j's representative } else { this.parent[irep] = jrep; // Make j's representative parent of i's representative this.rank[jrep]++; // Increment the rank of the resulting set }> |
>
>
Union par taille :
Encore une fois, nous avons besoin d’un nouveau tableau d’entiers appelé taille[] . La taille de ce tableau est la même que celle du tableau parent Parent[] . Si je suis le représentant d'un ensemble, taille[i] est le nombre d'éléments dans l'arborescence représentant l'ensemble.
Maintenant nous réunissons deux arbres (ou ensembles), appelons-les gauche et droite, alors dans ce cas tout dépend de la taille de gauche et le taille du droit arbre (ou ensemble).
- Si la taille de gauche est inférieur à la taille de droite , alors il vaut mieux déménager gauche sous droite et augmentez la taille de la droite par la taille de la gauche. De la même manière, si la taille de droite est inférieure à la taille de gauche, alors nous devrions nous déplacer juste en dessous de la gauche. et augmentez la taille de la gauche par la taille de la droite.
- Si les tailles sont égales, peu importe quel arbre passe sous l’autre.
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]++; } } }> |
>
>Sortir
Element 0: Representative = 0 Element 1: Representative = 0 Element 2: Representative = 2 Element 3: Representative = 2 Element 4: Representative = 0>
Complexité temporelle : O(log n) sans compression de chemin.
Vous trouverez ci-dessous l'implémentation complète de l'ensemble disjoint avec compression de chemin et union par rang.
C++
// C++ implementation of disjoint set> > #include> using> namespace> std;> > class> DisjSet {> >int> *rank, *parent, n;> > public>:> > >// Constructor to create and> >// initialize sets of n items> >DisjSet(>int> n)> >{> >rank =>new> int>[n];> >parent =>new> int>[n];> >this>->n = n;> >makeSet();> >}> > >// Creates n single item sets> >void> makeSet()> >{> >for> (>int> i = 0; i parent[i] = i; } } // Finds set of given item x int find(int x) { // Finds the representative of the set // that x is an element of if (parent[x] != x) { // if x is not the parent of itself // Then x is not the representative of // his set, parent[x] = find(parent[x]); // so we recursively call Find on its parent // and move i's node directly under the // representative of this set } return parent[x]; } // Do union of two sets by rank represented // by x and y. void Union(int x, int y) { // Find current sets of x and y int xset = find(x); int yset = find(y); // If they are already in same set if (xset == yset) return; // Put smaller ranked item under // bigger ranked item if ranks are // different if (rank[xset] parent[xset] = yset; } else if (rank[xset]>rang[yset]) { parent[yset] = xset; } // Si les rangs sont identiques, alors incrémentez // le rang. sinon { parent[yset] = xset; rang[xset] = rang[xset] + 1 ; } } } ; // Code du pilote int main() { // Appel de fonction DisjSet obj(5); obj.Union(0, 2); obj.Union(4, 2); obj.Union(3, 1); si (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'>);> }> |
>
>Sortir
Yes No>
Complexité temporelle : O(n) pour créer n ensembles d'éléments uniques. Les deux techniques - compression de chemin avec l'union par rang/taille, la complexité temporelle atteindra un temps presque constant. Il s'avère que la finale complexité du temps amorti est O(α(n)), où α(n) est la fonction d'Ackermann inverse, qui croît très régulièrement (elle ne dépasse même pas pour n<10600environ).
Complexité spatiale : O(n) car nous devons stocker n éléments dans la structure de données de l'ensemble disjoint.