-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDisjSets.cpp
More file actions
59 lines (52 loc) · 1.63 KB
/
DisjSets.cpp
File metadata and controls
59 lines (52 loc) · 1.63 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "DisjSets.h"
/**
* Construct the disjoint sets object.
* numElements is the initial number of disjoint sets.
*/
DisjSets::DisjSets( int numElements ) : s( numElements )
{
for( int i = 0; i < s.size( ); i++ )
s[ i ] = -1;
}
/**
* Union two disjoint sets.
* For simplicity, we assume root1 and root2 are distinct
* and represent set names.
* root1 is the root of set 1.
* root2 is the root of set 2.
*/
void DisjSets::unionSets( int root1, int root2 )
{
if( s[ root2 ] < s[ root1 ] ) // root2 is deeper
s[ root1 ] = root2; // Make root2 new root
else
{
if( s[ root1 ] == s[ root2 ] )
s[ root1 ]--; // Update height if same
s[ root2 ] = root1; // Make root1 new root
}
}
/**
* Perform a find.
* Error checks omitted again for simplicity.
* Return the set containing x.
*/
int DisjSets::find( int x ) const
{
if( s[ x ] < 0 )
return x;
else
return find( s[ x ] );
}
/**
* Perform a find with path compression.
* Error checks omitted again for simplicity.
* Return the set containing x.
*/
int DisjSets::find( int x )
{
if( s[ x ] < 0 )
return x;
else
return s[ x ] = find( s[ x ] );
}