union_find.c File Reference

Union find algorithm. More...

#include <stdio.h>
#include <stdlib.h>

Include dependency graph for union_find.c:

Macros
#define	MAX_SIZE   1000
	maximum number of elements in the set

Functions
int	find (int *p, int x)
	Find index of or value in an array. More...
void	join (int *p, int x, int y)
	Function to join. More...
int	main ()
	Main function.

Detailed Description

Union find algorithm.

Function Documentation

find()

int find	(	int *	p,
		int	x
	)

Find index of or value in an array.

Parameters

[in,out]	p	array to search and update
	x	value to search

Returns

value at the index x

{
    if (x >= MAX_SIZE)
    {
        fprintf(stderr, "Out-of bounds value\n");
        exit(EXIT_FAILURE);
    }
 
    if (p[x] == x)
    {
        return x;
    }
    else
    {
        p[x] = find(p, p[x]);
        return p[x];
    }
}

join()

void join	(	int *	p,
		int	x,
		int	y
	)

Function to join.

Parameters

[in,out]	p	array to join in
	x	value or index to join to
	y	value or index to join from

{ p[find(p, x)] = find(p, y); }

Here is the call graph for this function: