Union Find

An Introduction to Union Find : http://www.algorithmist.com/index.php/Union_Find

The most optimized implementation :

	#include <iostream>
	static const int N = 10000;
	int main()
	{ int i, j, p, q, id[N], sz[N];
	for (i = 0; i < N; i++)
	{ id[i] = i; sz[i] = 1; }
	while (cin >> p >> q)
	{
	for (i = p; i != id[i]; i = id[i])
	id[i] = id[id[i]];
	for (j = q; j != id[j]; j = id[j])
	id[j] = id[id[j]];
	if (i == j) continue;
	if (sz[i] < sz[j])
	{ id[i] = j; sz[j] += sz[i]; }
	else { id[j] = i; sz[i] += sz[j]; }
	cout << " " << p << " " << q << endl;
	}
	}

view raw union_find.cpp hosted with ❤ by GitHub

Code borrowed from : http://www.cs.princeton.edu/~rs/Algs3.cxx1-4/code.txt