Considere una situación con varias personas y las siguientes tareas que deben realizarse en ellas.
- Agregue una nueva relación de amistad, es decir, una persona x se vuelve amiga de otra persona y.
- Averigüe si el individuo x es amigo del individuo y (amigo directo o indirecto)
Ejemplo:
We are given 10 individuals say,
a, b, c, d, e, f, g, h, i, j
Following are relationships to be added.
a <-> b
b <-> d
c <-> f
c <-> i
j <-> e
g <-> j
And given queries like whether a is a friend of d
or not.
We basically need to create following 4 groups
and maintain a quickly accessible connection
among group items:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e, g, j}
G4 = {h}
Problema: Encontrar si xey pertenecen al mismo grupo o no, es decir, averiguar si xey son amigos directos/indirectos.
Solución: dividir a los individuos en diferentes conjuntos según los grupos en los que se encuentran. Este método se conoce como estructura de datos de conjuntos disjuntos que mantiene una colección de conjuntos disjuntos y cada conjunto está representado por su representante, que es uno de sus miembros.
Acercarse:
- ¿Cómo resolver conjuntos? Inicialmente todos los elementos pertenecen a conjuntos diferentes. Después de trabajar en las relaciones dadas, seleccionamos un miembro como representante. Puede haber muchas formas de seleccionar un representante, una simple es seleccionar con el índice más grande.
- Comprobar si hay 2 personas en el mismo grupo. Si los representantes de dos personas son iguales, entonces se harán amigos.
Estructuras de datos utilizadas:
Array: una array de enteros, llamada parent[]. Si estamos tratando con n elementos, el i-ésimo elemento de la array representa el i-ésimo elemento. Más precisamente, el i-ésimo elemento de la array es el padre del i-ésimo elemento. Estas relaciones crean uno o más árboles virtuales.
Árbol: Es un conjunto disjunto. Si dos elementos están en el mismo árbol, entonces están en el mismo conjunto disjunto. El Node raíz (o el Node superior) de cada árbol se denomina representante del conjunto. Siempre hay un único representante único de cada conjunto. Una regla simple para identificar a un representante es si ‘i’ es el representante de un conjunto, entonces padre[i] = i. Si i no es el representante de su conjunto, se puede encontrar subiendo por el árbol hasta que encontremos al representante.
operaciones:
Find : se puede implementar recorriendo recursivamente la array principal hasta que lleguemos a un Node que sea padre de sí mismo.
// Finds the representative of the set
// that i is an element of
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]);
}
}
Unión: Toma, como entrada, dos elementos. Y encuentra los representantes de sus conjuntos mediante la operación de búsqueda y finalmente coloca uno de los árboles (que representa el conjunto) debajo del Node raíz del otro árbol, fusionando efectivamente los árboles y los conjuntos.
// Unites the set that includes i
// and the set that includes j
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;
}
Mejoras (Unión por Rango y Compresión de Ruta)
La eficiencia depende mucho de la altura del árbol. Necesitamos minimizar la altura del árbol para mejorar la eficiencia. Podemos usar la compresión de ruta y la unión por métodos de clasificación para hacerlo.
Path Compression (Modificaciones a find()) : Acelera la estructura de datos al comprimir la altura de los árboles. Se puede lograr insertando un pequeño mecanismo de almacenamiento en caché en la operación de búsqueda. Echa un vistazo al código para más detalles:
// Finds the representative of the set that i
// is an element of.
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;
}
}
Unión por rango: en primer lugar, necesitamos una nueva array de números enteros llamada rango []. El tamaño de esta array es el mismo que el de la array principal. Si i es un representante de un conjunto, el rango[i] es la altura del árbol que representa el conjunto.
Ahora recuerde que, en la operación Unión, no importa cuál de los dos árboles se mueve debajo del otro (vea las dos últimas imágenes de ejemplo arriba). Ahora lo que queremos hacer es minimizar la altura del árbol resultante. Si estamos uniendo dos árboles (o conjuntos), llamémoslos izquierda y derecha, entonces todo depende del rango de la izquierda y el rango de la derecha.
- Si el rango de la izquierda es menor que el rango de la derecha, entonces es mejor mover la izquierda debajo de la derecha, porque eso no cambiará el rango de la derecha (mientras que mover la derecha debajo de la izquierda aumentaría la altura). De la misma manera, si el rango de la derecha es menor que el de la izquierda, entonces deberíamos mover la derecha debajo de la izquierda.
- Si los rangos son iguales, no importa qué árbol quede debajo del otro, pero el rango del resultado siempre será uno mayor que el rango de los árboles.
// Unites the set that includes i and the set
// that includes j
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);
// 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 < jrank)
{
// Then move i under j
this.parent[irep] = jrep;
}
// Else if j’s rank is less than i’s rank
else if (jrank < irank)
{
// 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]++;
}
}
C++
// C++ implementation of disjoint set
#include <iostream>
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 < n; 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 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] < rank[yset]) {
parent[xset] = yset;
}
else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
}
// If ranks are same, then increment
// rank.
else {
parent[yset] = xset;
rank[xset] = rank[xset] + 1;
}
}
};
int main()
{
DisjSet obj(5);
obj.Union(0, 2);
obj.Union(4, 2);
obj.Union(3, 1);
if (obj.find(4) == obj.find(0))
cout << "Yes\n";
else
cout << "No\n";
if (obj.find(1) == obj.find(0))
cout << "Yes\n";
else
cout << "No\n";
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 < n; 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] < rank[yRoot])
// 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] < rank[xRoot])
// 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
else if 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 < n; 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] < rank[yRoot])
// 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] < rank[xRoot])
// 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
Producción:
Yes No
Aplicaciones:
- Algoritmo de árbol de expansión mínimo de Kruskal .
- Problema de secuenciación de trabajos.
- Detección de ciclo
Artículos relacionados:
Algoritmo de búsqueda de unión | Conjunto 1 (Detectar ciclo en un gráfico no dirigido)
Algoritmo de búsqueda de unión | Conjunto 2 (Unión por rango y compresión de ruta)
Intente resolver este problema y verifique cuánto aprendió y comente sobre la complejidad de la pregunta dada.
Este artículo es una contribución de Nikhil Tekwani . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA