disjoint_set.cpp File Reference

Disjoint Sets Data Structure (Disjoint Sets) More...

#include <iostream>
#include <vector>

Include dependency graph for disjoint_set.cpp:

Go to the source code of this file.

Functions
void	CreateSet (int n)
int	Find (int x)
bool	InSameUnion (int x, int y)
void	Union (int x, int y)
int	main ()

Variables
vector< int >	root
vector< int >	rank

Detailed Description

Disjoint Sets Data Structure (Disjoint Sets)

Author

leoyang429

A disjoint set data structure (also called union find or merge find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. Some situations where disjoint sets can be used are- to find connected components of a graph, kruskal's algorithm for finding Minimum Spanning Tree etc. There are two operation which we perform on disjoint sets - 1) Union 2) Find

Definition in file disjoint_set.cpp.

Function Documentation

CreateSet()

void CreateSet

(

int

n

)

Function to create a set

Parameters

n	number of element

Definition at line 37 of file disjoint_set.cpp.

                      {
    root = vector<int>(n + 1);
    rank = vector<int>(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        root[i] = i;
    }
}

Find()

int Find

(

int

x

)

Find operation takes a number x and returns the set to which this number belongs to.

Parameters

x	element of some set

Returns

set to which x belongs to

Definition at line 53 of file disjoint_set.cpp.

                {
    if (root[x] == x) {
        return x;
    }
    return root[x] = Find(root[x]);
}

InSameUnion()

bool InSameUnion	(	int	x,
		int	y )

A utility function to check if x and y are from same set or not

Parameters

x	element of some set
y	element of some set

Definition at line 67 of file disjoint_set.cpp.

{ return Find(x) == Find(y); }

main()

int main

(

void

)

Main function

Definition at line 93 of file disjoint_set.cpp.

           {
    // tests CreateSet & Find
    int n = 100;
    CreateSet(n);
    for (int i = 1; i <= 100; ++i) {
        if (root[i] != i) {
            cout << "Fail" << endl;
            break;
        }
    }
    // tests InSameUnion & Union
    cout << "1 and 2 are initially not in the same subset" << endl;
    if (InSameUnion(1, 2)) {
        cout << "Fail" << endl;
    }
    Union(1, 2);
    cout << "1 and 2 are now in the same subset" << endl;
    if (!InSameUnion(1, 2)) {
        cout << "Fail" << endl;
    }
    return 0;
}

Union()

void Union	(	int	x,
		int	y )

Union operation combines two disjoint sets to make a single set in this union function we pass two elements and check if they are from different sets then combine those sets

Parameters

x	element of some set
y	element of some set

Definition at line 78 of file disjoint_set.cpp.

                         {
    int a = Find(x), b = Find(y);
    if (a != b) {
        if (rank[a] < rank[b]) {
            root[a] = b;
        } else if (rank[a] > rank[b]) {
            root[b] = a;
        } else {
            root[a] = b;
            ++rank[b];
        }
    }
}

Variable Documentation

rank

vector<int> rank

Definition at line 29 of file disjoint_set.cpp.

root

vector<int> root

Definition at line 29 of file disjoint_set.cpp.