Dynamic Disjoint Set Data Structure for large range values
Last Updated :
01 Aug, 2024
Prerequisites:
Disjoint Set data structure is used to keep track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
In this article, we will learn about constructing the same Data Structure dynamically. This data structure basically helps in situations where we cannot simply use arrays for creating disjoint sets because of large inputs of order 109.
To illustrate this, consider the following problem. We need to find the total number of connected components in the Graph when the total Number of Vertices can be up to 10^9.
Examples:
Input : Edges : { { 1, 2 },
{ 2, 3 },
{ 4, 5 } }
Output : 2
Explanation: {1, 2, 3} forms a component and
{4, 5} forms another component.The idea to solve this problem is, we will maintain two hash tables (implemented using unordered_maps in C++). One for parent and other for degree. Parent[V] will give the parent of the component which the Vertex V is part of and Degree will give the number of vertices in that component.
Initially, both Parent and Degree will be empty. We will keep inserting vertices to the maps as sequentially.
See the code and the explanation simultaneously for a better understanding. Below are the methods used in the code to solve the above problem:
- getParent(V): This method will give the parent of the vertex V. Here we recursively find the parent of the vertex V( see code), meanwhile we assign all the vertex in that component to have the same parent.( In a disjoint set data structure all the vertex in the same component have the same parent.)
- Union(): When we add an edge and the two vertexes are of different components we call the Union() method to join both components. Here the parent of the component formed after joining both components will be the parent of the component among the two which had more vertexes before the union. The degree of the new component is updated accordingly.
- getTotalComponent(): Vertex in the same component will have the same parent.
We use unordered_set (STL) to count the total number of components. As we have maintained the Data Structure as Dynamic, there can be any vertex that has not been added to any of the components hence they are different components alone. So the total number of components will be given by,
Total no of Component = Total Vertices - Number of Vertices
in parent (Map) + Number of Component
formed from the Vertexes inserted
in the graph.
Below is the implementation of the above idea:
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;
}
// Dynamic Disjoint Set Data Structure
// Union-Find
import java.util.*;
// Dynamic Disjoint Set Data Structure
class DynamicDisjointSetDS {
// We will add the vertex to the edge
// only when it is asked to i.e. maintain
// a dynamic DS.
Map<Integer, Integer> parent, degree;
// Total number of Vertex in the Graph
int N;
// Constructor
DynamicDisjointSetDS(int n)
{
N = n;
parent = new HashMap<>();
degree = new HashMap<>();
}
// Get Parent of vertex V
int getParent(int vertex)
{
// If the vertex is already inserted
// in the graph
if (parent.containsKey(vertex)) {
if (parent.get(vertex) != vertex) {
parent.put(vertex,
getParent(parent.get(vertex)));
return parent.get(vertex);
}
}
// if the vertex is operated for the first
// time
else {
// insert the vertex and assign its
// parent to itself
parent.put(vertex, vertex);
// Degree of the vertex
degree.put(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.get(x) > degree.get(y)) {
parent.put(y, x);
degree.put(x, degree.get(x) + degree.get(y));
}
else {
parent.put(x, y);
degree.put(y, degree.get(y) + degree.get(x));
}
}
// Count total Component in the Graph
int getTotalComponent()
{
// To count the total Component formed
// from the inserted vertex in the Graph
Set<Integer> total = new HashSet<>();
// Iterate through the parent
for (Map.Entry<Integer, Integer> entry :
parent.entrySet()) {
// Add the parent of each Vertex
// to the set
total.add(getParent(entry.getKey()));
}
// 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();
}
}
// Driver Code
public class Main {
public static void main(String[] args)
{
// Total Number of Vertexes
int N = 5;
/* Edges
* 1 <--> 2
* 2 <--> 3
* 4 <--> 5 */
int[][] Edges = { { 1, 2 }, { 2, 3 }, { 4, 3 } };
DynamicDisjointSetDS dsu
= new DynamicDisjointSetDS(N);
for (int i = 0; i < 3; i++) {
if (dsu.getParent(Edges[i][0])
== dsu.getParent(Edges[i][1])) {
continue;
}
else {
dsu.union(Edges[i][0], Edges[i][1]);
}
}
System.out.println(dsu.getTotalComponent());
}
}
# 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
// Dynamic Disjoint Set Data Structure
// Union-Find
using System;
using System.Collections.Generic;
public class GFG {
static int N;
static int[, ] Edges = new int[3, 2];
// Dynamic Disjoint Set Data Structure
public class DynamicDisjointSetDS {
// We will add the vertex to the edge
// only when it is asked to i.e. maintain
// a dynamic DS.
Dictionary<int, int> parent
= new Dictionary<int, int>();
Dictionary<int, int> degree
= new Dictionary<int, int>();
// Total number of Vertex in the Graph
int N;
// Constructor
public DynamicDisjointSetDS(int n) { N = n; }
// Get Parent of vertex V
public int GetParent(int vertex)
{
// If the vertex is already inserted
// in the graph
if (parent.ContainsKey(vertex)) {
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[vertex] = vertex;
// Degree of the vertex
degree[vertex] = 1;
}
return vertex;
}
// Union by Rank
public 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[y];
}
else {
parent[x] = y;
degree[y] += degree[x];
}
}
// Count total Component in the Graph
public int GetTotalComponent()
{
// To count the total Component formed
// from the inserted vertex in the Graph
HashSet<int> total = new HashSet<int>();
// Iterate through the parent
foreach(int key in new List<int>(parent.Keys))
{
// Add the parent of each Vertex
// to the set
total.Add(GetParent(key));
}
// Total Component = Total Vertexes -
// Number of Vertex in the parent +
// Number of Component formed from
// the Vertexes inserted in the Graph
return N - parent.Count + total.Count;
}
}
// Solve
public static void Solve()
{
// Declaring the Dynamic Disjoint Set DS
DynamicDisjointSetDS dsu
= new DynamicDisjointSetDS(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
Console.WriteLine(dsu.GetTotalComponent());
}
// Driver Code
public static void 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();
}
}
// This code is contributed by prasad264
// Dynamic Disjoint Set Data Structure
// Union-Find
const N = 5;
const Edges = [[1, 2], [2, 3], [4, 5]];
// Dynamic Disjoint Set Data Structure
class DynamicDisjointSetDS {
// Constructor
constructor(n) {
this.N = n;
this.parent = new Map();
this.degree = new Map();
}
// Get Parent of vertex V
getParent(vertex) {
// If the vertex is already inserted
// in the graph
if (this.parent.has(vertex)) {
if (this.parent.get(vertex) !== vertex) {
this.parent.set(vertex, this.getParent(this.parent.get(vertex)));
return this.parent.get(vertex);
}
}
// if the vertex is operated for the first
// time
else {
// insert the vertex and assign its
// parent to itself
this.parent.set(vertex, vertex);
// Degree of the vertex
this.degree.set(vertex, 1);
}
return vertex;
}
// Union by Rank
Union(vertexA, vertexB) {
// Parent of Vertex A
const x = this.getParent(vertexA);
// Parent of Vertex B
const y = this.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 (this.degree.get(x) > this.degree.get(y)) {
this.parent.set(y, x);
this.degree.set(x, this.degree.get(x) + this.degree.get(y));
} else {
this.parent.set(x, y);
this.degree.set(y, this.degree.get(y) + this.degree.get(x));
}
}
// Count total Component in the Graph
GetTotalComponent() {
// To count the total Component formed
// from the inserted vertex in the Graph
const total = new Set();
// Iterate through the parent
for (const [key, value] of this.parent) {
// Add the parent of each Vertex
// to the set
total.add(this.getParent(key));
}
// Total Component = Total Vertexes -
// Number of Vertex in the parent +
// Number of Component formed from
// the Vertexes inserted in the Graph
return this.N - this.parent.size + total.size;
}
}
// Solve
function solve() {
// Declaring the Dynamic Disjoint Set DS
const dsu = new DynamicDisjointSetDS(N);
// Traversing through the Edges
for (let i = 0; i < Edges.length; 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
console.log(dsu.GetTotalComponent());
}
// Driver Code
solve();
Output:
2
Time Complexity: O(E * alpha(N)), where E is the number of edges in the graph, N is the number of vertices in the graph, and alpha is the inverse Ackermann function, which has a value less than 5 for all practical values of N.
Space Complexity: O(N), where N is the total number of vertices in the graph.
Note: If the number of vertices is even larger, we can implement the same code just by changing the data type from int to long.
Similar Reads
DSA Tutorial - Learn Data Structures and Algorithms
DSA (Data Structures and Algorithms) is the study of organizing data efficiently using data structures like arrays, stacks, and trees, paired with step-by-step procedures (or algorithms) to solve problems effectively. Data structures manage how data is stored and accessed, while algorithms focus on
7 min read
Quick Sort
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array. It works on the principle of divide and conquer, breaking down the problem into s
12 min read
Merge Sort - Data Structure and Algorithms Tutorials
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer approach. It works by recursively dividing the input array into two halves, recursively sorting the two halves and finally merging them back together to obtain the sorted array. Merge
14 min read
Breadth First Search or BFS for a Graph
Given a undirected graph represented by an adjacency list adj, where each adj[i] represents the list of vertices connected to vertex i. Perform a Breadth First Search (BFS) traversal starting from vertex 0, visiting vertices from left to right according to the adjacency list, and return a list conta
15+ min read
Bubble Sort Algorithm
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.We sort the array using multiple passes. After the fir
8 min read
Binary Search Algorithm - Iterative and Recursive Implementation
Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N). Binary Search AlgorithmConditions to apply Binary Searc
15 min read
Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. T
9 min read
Data Structures Tutorial
Data structures are the fundamental building blocks of computer programming. They define how data is organized, stored, and manipulated within a program. Understanding data structures is very important for developing efficient and effective algorithms. What is Data Structure?A data structure is a st
2 min read
Dijkstra's Algorithm to find Shortest Paths from a Source to all
Given a weighted undirected graph represented as an edge list and a source vertex src, find the shortest path distances from the source vertex to all other vertices in the graph. The graph contains V vertices, numbered from 0 to V - 1.Note: The given graph does not contain any negative edge. Example
12 min read
Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted.First we find the smallest element an
8 min read