A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d3/dae/dsu__path__compression_8cpp.html below:

TheAlgorithms/C++: data_structures/dsu_path_compression.cpp File Reference

Loading...

Searching...

No Matches

DSU (Disjoint sets) More...

#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...
static void  test1 ()   Self-test implementations, 1st test.
static void  test2 ()   Self-implementations, 2nd test.
int  main ()   Main function.

DSU (Disjoint sets)

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.

See also
dsu_union_rank.cpp

Definition in file dsu_path_compression.cpp.

◆ main()

Main function.

Returns
0 on exit

< 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.

Returns
void

< 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 }

181

cout <<

"1st test passed!"

<<

endl

;

182}

◆ test2()

Self-implementations, 2nd test.

Returns
void

< 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 }

199

cout <<

"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