union Find Algorithm
It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether components are in the same set. In computer science, a disjoint-put data structure (also named a union – find data structure or merge – find put) is a data structure that tracks a set of components partitioned into a number of disjoint (non-overlapping) subsets. In 2007, Sylvain Conchon and Jean-Christophe Filliâtre developed a persistent version of the disjoint-put forest data structure, letting previous versions of the structure to be efficiently retained, and formalized its correctness use the proof assistant Coq. In 1994, Richard J. Anderson and Heather Woll described a parallelized version of Union – Find that never needs to block. In 1991, Galil and Italiano published a survey of data structures for disjoint-sets.
#include <stdio.h>
int p[1000000];
int find(int x)
{
if (p[x] == x)
{
return x;
}
else
{
p[x] = find(p[x]);
return p[x];
}
}
// Call to function join(int x, int y) to join PARAM x and y
void join(int x, int y)
{
p[find(x)] = find(y);
}
int main()
{
// Have all array indexes that you need to use refrence themselves
for (int i = 0; i < 10; i++)
{
p[i] = i;
}
// p = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
join(3, 5);
// Now 3 and 5 are groupped together, that is find(3) = find(5)
// p = {0, 1, 2, 5, 4, 5, 6, 7, 8, 9}
join(3, 8);
// Now 3, 5 and are groupped together, find(3) = find(5) = find(8)
// p = {0, 1, 2, 5, 4, 8, 6, 7, 8, 9}
join(0, 5);
if(find(0) == find(3))
{
printf("0 and 3 are groupped together\n");
}
printf("The array is now: ");
for(int i = 0; i < 10; i++)
{
printf("%d ", p[i]);
}
printf("\n");
return 0;
}
