Loading...
Searching...
No Matches
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
Go to the source code of this file.
class dsu Disjoint sets union data structure, class based representation. More...It is a very powerful data structure that keeps track of different clusters(sets) of elements, these sets are disjoint(doesnot have a common element). Disjoint sets uses cases : for finding connected components in a graph, used in Kruskal's algorithm for finding Minimum Spanning tree. Operations that can be performed: 1) UnionSet(i,j): add(element i and j to the set) 2) findSet(i): returns the representative of the set to which i belogngs to. 3) get_max(i),get_min(i) : returns the maximum and minimum Below is the class-based approach which uses the heuristic of path compression. Using path compression in findSet(i),we are able to get to the representative of i in O(1) time.
Definition in file dsu_path_compression.cpp.
◆ main()Main function.
< number of items
< object of class disjoint sets
Definition at line 206 of file dsu_path_compression.cpp.
206 {
207 uint64_t n = 10;
209
212
213 return 0;
214}
Disjoint sets union data structure, class based representation.
static void test2()
Self-implementations, 2nd test.
static void test1()
Self-test implementations, 1st test.
◆ test1()Self-test implementations, 1st test.
< number of items
< object of class disjoint sets
Definition at line 170 of file dsu_path_compression.cpp.
170 {
171
172 uint64_t n = 10;
174
175 d.UnionSet(1, 2);
176 d.UnionSet(1, 4);
177 vector<uint64_t> ans = {1, 4, 3};
178 for (uint64_t i = 0; i < ans.size(); i++) {
179 assert(d.get(4).at(i) == ans[i]);
180 }
181cout <<
"1st test passed!"<<
endl;
182}
◆ test2()Self-implementations, 2nd test.
< number of items
< object of class disjoint sets
Definition at line 187 of file dsu_path_compression.cpp.
187 {
188
189 uint64_t n = 10;
191
192 d.UnionSet(3, 5);
193 d.UnionSet(5, 6);
194 d.UnionSet(5, 7);
195 vector<uint64_t> ans = {3, 7, 4};
196 for (uint64_t i = 0; i < ans.size(); i++) {
197 assert(d.get(3).at(i) == ans[i]);
198 }
199cout <<
"2nd test passed!"<<
endl;
200}
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4