requisitos previos:
La estructura de datos del conjunto disjunto se utiliza para realizar un seguimiento de un conjunto de elementos divididos en varios subconjuntos disjuntos (que no se superponen).
En este artículo, aprenderemos a construir dinámicamente la misma estructura de datos. Esta estructura de datos básicamente ayuda en situaciones en las que simplemente no podemos usar arreglos para crear conjuntos disjuntos debido a grandes entradas de orden 10 9 .
Para ilustrar esto, considere el siguiente problema. Necesitamos encontrar el número total de componentes conectados en el gráfico cuando el número total de vértices puede ser hasta 10^9.
Ejemplos:
Input : Edges : { { 1, 2 },
{ 2, 3 },
{ 4, 5 } }
Output : 2
Explanation: {1, 2, 3} forms a component and
{4, 5} forms another component.
La idea para resolver este problema es que mantendremos dos tablas hash (implementadas usando unordered_maps en C++). Uno para padres y otro para grado . Padre[V] dará el padre del componente del que forma parte el Vértice V y Grado dará el número de vértices en ese componente.
Inicialmente, tanto Padre como Título estarán vacíos. Seguiremos insertando vértices en los mapas de forma secuencial.
Ver el código y la explicación simultáneamente para una mejor comprensión. A continuación se muestran los métodos utilizados en el código para resolver el problema anterior:
- getParent(V): Este método dará el padre del vértice V. Aquí encontramos recursivamente el padre del vértice V (ver código), mientras tanto asignamos todos los vértices en ese componente para tener el mismo padre. (En un conjunto disjunto estructura de datos todos los vértices en el mismo componente tienen el mismo padre).
- Union(): cuando agregamos un borde y los dos vértices son de componentes diferentes, llamamos al método Union() para unir ambos componentes. Aquí el padre del componente formado después de unir ambos componentes será el padre del componente entre los dos que tenía más número de vértices antes de la unión. El grado del nuevo componente se actualiza en consecuencia.
- getTotalComponent(): el vértice en el mismo componente tendrá el mismo padre.
Usamos unordered_set (STL) para contar el número total de componentes. Como hemos mantenido la estructura de datos como dinámica, puede haber cualquier vértice que no se haya agregado a ninguno de los componentes, por lo que son componentes diferentes solos. Entonces el número total de componentes estará dado por,
Total no of Component = Total Vertices - Number of Vertices
in parent (Map) + Number of Component
formed from the Vertexes inserted
in the graph.
A continuación se muestra la implementación de la idea anterior:
C++
// Dynamic Disjoint Set Data Structure
// Union-Find
#include <bits/stdc++.h>
using namespace std;
int N;
int Edges[3][2];
// Dynamic Disjoint Set Data Structure
struct DynamicDisjointSetDS {
// We will add the vertex to the edge
// only when it is asked to i.e. maintain
// a dynamic DS.
unordered_map<int, int> parent, degree;
// Total number of Vertex in the Graph
int N;
// Constructor
DynamicDisjointSetDS(int n)
{
N = n;
}
// Get Parent of vertex V
int getParent(int vertex)
{
// If the vertex is already inserted
// in the graph
if (parent.find(vertex) != parent.end()) {
if (parent[vertex] != vertex) {
parent[vertex] =
getParent(parent[vertex]);
return parent[vertex];
}
}
// if the vertex is operated for the first
// time
else {
// insert the vertex and assign its
// parent to itself
parent.insert(make_pair(vertex, vertex));
// Degree of the vertex
degree.insert(make_pair(vertex, 1));
}
return vertex;
}
// Union by Rank
void Union(int vertexA, int vertexB)
{
// Parent of Vertex A
int x = getParent(vertexA);
// Parent of Vertex B
int y = getParent(vertexB);
// if both have same parent
// Do Nothing
if (x == y)
return;
// Merging the component
// Assigning the parent of smaller Component
// as the parent of the bigger Component.
if (degree[x] > degree[y]) {
parent[y] = x;
degree[x] = degree[x] + degree[y];
}
else {
parent[x] = y;
degree[y] = degree[y] + degree[x];
}
}
// Count total Component in the Graph
int GetTotalComponent()
{
// To count the total Component formed
// from the inserted vertex in the Graph
unordered_set<int> total;
// Iterate through the parent
for (auto itr = parent.begin();
itr != parent.end(); itr++) {
// Add the parent of each Vertex
// to the set
total.insert(getParent(itr->first));
}
// Total Component = Total Vertexes -
// Number of Vertex in the parent +
// Number of Component formed from
// the Vertexes inserted in the Graph
return N - parent.size() + total.size();
}
};
// Solve
void Solve()
{
// Declaring the Dynamic Disjoint Set DS
DynamicDisjointSetDS dsu(N);
// Traversing through the Edges
for (int i = 0; i < 3; i++) {
// If the Vertexes in the Edges
// have same parent do nothing
if (dsu.getParent(Edges[i][0]) ==
dsu.getParent(Edges[i][1])) {
continue;
}
// else Do Union of both the Components.
else {
dsu.Union(Edges[i][0], Edges[i][1]);
}
}
// Get total Components
cout << dsu.GetTotalComponent();
}
// Driver Code
int main()
{
// Total Number of Vertexes
N = 5;
/* Edges
* 1 <--> 2
* 2 <--> 3
* 4 <--> 5 */
Edges[0][0] = 1;
Edges[0][1] = 2;
Edges[1][0] = 2;
Edges[1][1] = 3;
Edges[2][0] = 4;
Edges[2][1] = 3;
// Solve
Solve();
return 0;
}
Python3
# Dynamic Disjoint Set Data Structure
# Union-Find
# Dynamic Disjoint Set Data Structure
class DynamicDisjointSetDS:
# Constructor
def __init__(self, n):
# Total number of Vertex in the Graph
self.N = n
# We will add the vertex to the edge
# only when it is asked to i.e. maintain
# a dynamic DS.
self.parent = {}
self.degree = {}
# Get Parent of vertex V
def getParent(self, vertex):
# If the vertex is already inserted
# in the graph
if vertex in self.parent:
if self.parent[vertex] != vertex:
self.parent[vertex] = \
self.getParent(self.parent[vertex])
return self.parent[vertex]
# if the vertex is operated
# for the first time
else:
# insert the vertex and assign
# its parent to itself
self.parent[vertex] = vertex
# Degree of the vertex
self.degree[vertex] = 1
return vertex
# Union by Rank
def Union(self, vertexA, vertexB):
# Parent of Vertex A
x = self.getParent(vertexA)
# Parent of Vertex B
y = self.getParent(vertexB)
# if both have same parent
# Do Nothing
if x == y:
return
# Merging the component
# Assigning the parent of smaller Component
# as the parent of the bigger Component.
if self.degree[x] > self.degree[y]:
self.parent[y] = x
self.degree[x] = (self.degree[x] +
self.degree[y])
else:
self.parent[x] = y
self.degree[y] = (self.degree[y] +
self.degree[x])
# Count total Component in the Graph
def GetTotalComponent(self):
# To count the total Component formed
# from the inserted vertex in the Graph
total = set()
# Iterate through the parent
for itr in self.parent:
# Add the parent of each Vertex
# to the set
total.add(self.getParent(itr))
# Total Component = Total Vertexes -
# Number of Vertex in the parent +
# Number of Component formed from
# the Vertexes inserted in the Graph
return self.N - len(self.parent) + len(total)
# Solve
def Solve(N):
# Declaring the Dynamic Disjoint Set DS
dsu = DynamicDisjointSetDS(N)
# Traversing through the Edges
for i in range(0, 3):
# If the Vertexes in the Edges
# have same parent do nothing
if (dsu.getParent(Edges[i][0]) ==
dsu.getParent(Edges[i][1])):
continue
# else Do Union of both the Components.
else:
dsu.Union(Edges[i][0], Edges[i][1])
# Get total Components
print(dsu.GetTotalComponent())
# Driver Code
if __name__ == "__main__":
# Total Number of Vertexes
N = 5
Edges = [[1, 2], [2, 3], [4, 3]]
# Solve
Solve(N)
# This code is contributed by
# Rituraj Jain
Producción:
2
Nota: si el número de vértices es aún mayor, podemos implementar el mismo código simplemente cambiando el tipo de datos de int a long.