Disjoint sets union data structure, class based representation.
More...

 dsu (uint64_t n) 
 contructor for initialising all data members.


uint64_t  findSet (uint64_t i) 
 Method to find the representative of the set to which i belongs to, T(n) = O(1)


void  UnionSet (uint64_t i, uint64_t j) 
 Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.


bool  isSame (uint64_t i, uint64_t j) 
 A utility function which check whether i and j belongs to same set or not.


vector< uint64_t >  get (uint64_t i) 
 prints the minimum, maximum and size of the set to which i belongs to


uint64_t  size (uint64_t i) 
 A utility function that returns the size of the set to which i belongs to.


uint64_t  get_max (uint64_t i) 
 A utility function that returns the max element of the set to which i belongs to.


uint64_t  get_min (uint64_t i) 
 A utility function that returns the min element of the set to which i belongs to.


 dsu (uint64_t n) 
 constructor for initialising all data members


uint64_t  findSet (uint64_t i) 
 Method to find the representative of the set to which i belongs to, T(n) = O(logN)


void  unionSet (uint64_t i, uint64_t j) 
 Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.


bool  isSame (uint64_t i, uint64_t j) 
 A utility function which check whether i and j belongs to same set or not.


vector< uint64_t >  getParents (uint64_t i) 
 Method to print all the parents of i, or the path from i to representative.



vector< uint64_t >  p 
 keeps track of the parent of ith element


vector< uint64_t >  depth 
 tracks the depth(rank) of i in the tree


vector< uint64_t >  setSize 
 size of each chunk(set)


vector< uint64_t >  maxElement 
 maximum of each set to which i belongs to


vector< uint64_t >  minElement 
 minimum of each set to which i belongs to


Disjoint sets union data structure, class based representation.
 Parameters

◆ dsu() [1/2]
contructor for initialising all data members.
 Parameters

initially, all of them are their own parents
initially all have depth are equals to zero
initially set size will be equals to one
45 {
47
48 for (uint64_t i = 0; i < n; i++) {
50 }
51
55 for (uint64_t i = 0; i < n; i++) {
59 }
61
62 for (uint64_t i = 0; i < n; i++) {
64 }
65 }
vector< uint64_t > minElement
minimum of each set to which i belongs to
Definition dsu_path_compression.cpp:39
vector< uint64_t > p
keeps track of the parent of ith element
Definition dsu_path_compression.cpp:35
vector< uint64_t > maxElement
maximum of each set to which i belongs to
Definition dsu_path_compression.cpp:38
vector< uint64_t > depth
tracks the depth(rank) of i in the tree
Definition dsu_path_compression.cpp:36
vector< uint64_t > setSize
size of each chunk(set)
Definition dsu_path_compression.cpp:37
◆ dsu() [2/2]
constructor for initialising all data members
 Parameters

initially all of them are their own parents
44 {
46
49 for (uint64_t i = 0; i < n; i++) {
53 }
54 }
◆ findSet() [1/2]
uint64_t dsu::findSet 
( 
uint64_t  i  ) 


inline 
Method to find the representative of the set to which i belongs to, T(n) = O(1)
 Parameters

 Returns
 representative of the set to which i belongs to.
using path compression
73 {
74
76 return i;
77 }
79 }
uint64_t findSet(uint64_t i)
Method to find the representative of the set to which i belongs to, T(n) = O(1)
Definition dsu_path_compression.cpp:73
◆ findSet() [2/2]
uint64_t dsu::findSet 
( 
uint64_t  i  ) 


inline 
Method to find the representative of the set to which i belongs to, T(n) = O(logN)
 Parameters

 Returns
 representative of the set to which i belongs to
using unionrank
61 {
62
65 }
66 return i;
67 }
◆ get()
vector< uint64_t > dsu::get 
( 
uint64_t  i  ) 


inline 
prints the minimum, maximum and size of the set to which i belongs to
 Parameters

 Returns
 void
135 {
139 ans.push_back(
size(i));
140 return ans;
141 }
uint64_t size(uint64_t i)
A utility function that returns the size of the set to which i belongs to.
Definition dsu_path_compression.cpp:148
uint64_t get_max(uint64_t i)
A utility function that returns the max element of the set to which i belongs to.
Definition dsu_path_compression.cpp:155
uint64_t get_min(uint64_t i)
A utility function that returns the min element of the set to which i belongs to.
Definition dsu_path_compression.cpp:162
◆ get_max()
uint64_t dsu::get_max 
( 
uint64_t  i  ) 


inline 
A utility function that returns the max element of the set to which i belongs to.
 Parameters

 Returns
 maximum of the set to which i belongs to
◆ get_min()
uint64_t dsu::get_min 
( 
uint64_t  i  ) 


inline 
A utility function that returns the min element of the set to which i belongs to.
 Parameters

 Returns
 minimum of the set to which i belongs to
◆ getParents()
vector< uint64_t > dsu::getParents 
( 
uint64_t  i  ) 


inline 
Method to print all the parents of i, or the path from i to representative.
 Parameters

 Returns
 void
119 {
122 ans.push_back(i);
124 }
125 ans.push_back(i);
126 return ans;
127 }
◆ isSame() [1/2]
bool dsu::isSame 
( 
uint64_t  i, 


uint64_t  j ) 

inline 
A utility function which check whether i and j belongs to same set or not.
 Parameters

i  element of some set 
j  element of some set 
 Returns
true
if element i
and j
ARE in the same set

false
if element i
and j
are NOT in same set
123 {
125 return true;
126 }
127 return false;
128 }
◆ isSame() [2/2]
bool dsu::isSame 
( 
uint64_t  i, 


uint64_t  j ) 

inline 
A utility function which check whether i and j belongs to same set or not.
 Parameters

i  element of some set 
j  element of some set 
 Returns
true
if element i and j are in same set

false
if element i and j are not in same set
107 {
109 return true;
110 }
111 return false;
112 }
◆ size()
uint64_t dsu::size 
( 
uint64_t  i  ) 


inline 
A utility function that returns the size of the set to which i belongs to.
 Parameters

 Returns
 size of the set to which i belongs to
◆ UnionSet()
void dsu::UnionSet 
( 
uint64_t  i, 


uint64_t  j ) 

inline 
Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.
 Parameters

i  element of some set 
j  element of some set 
 Returns
 void
check if both belongs to the same set or not
always keeping the min as x shallow tree
making the shallower root's parent the deeper root
if same depth, then increase one's depth
total size of the resultant set
changing the maximum elements
87 {
88
90 return;
91 }
92
93
96
97
98
101 }
102
104
105
108 }
109
111
114 }
bool isSame(uint64_t i, uint64_t j)
A utility function which check whether i and j belongs to same set or not.
Definition dsu_path_compression.cpp:123
◆ unionSet()
void dsu::unionSet 
( 
uint64_t  i, 


uint64_t  j ) 

inline 
Method that combines two disjoint sets to which i and j belongs to and make a single set having a common representative.
 Parameters

i  element of some set 
j  element of some set 
 Returns
 void
checks if both belongs to same set or not
we find representative of the i and j
always keeping the min as x in order to create a shallow tree
making the shallower tree, root parent of the deeper root
if same depth, then increase one's depth
total size of the resultant set
75 {
76
78 return;
79 }
80
83
84
85
88 }
89
91
92
95 }
96
98 }
The documentation for this class was generated from the following files: