disjoint_set.cpp File Reference

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

#include <iostream>
#include <vector>

Include dependency graph for disjoint_set.cpp:

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

Function Documentation

CreateSet()

void CreateSet

(

int

n

)

Function to create a set

Parameters

n	number of element

                      {
    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

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

Here is the call graph for this function:

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

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

Here is the call graph for this function:

main()

int main

(

void

)

Main function

           {
    // 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;
}

Here is the call graph for this function:

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

                         {
    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];
        }
    }
}

Here is the call graph for this function: