Quick Union/Lazy Union

	//Lazy union
	class QuickUnion
	{
	int* arr;
	public:
	QuickUnion(int num)
	{
	size = num;
	arr = new int[num];
	//N array access
	for (int i = 0; i < num; i++)
	arr[i] = i;
	}
	int root(int i)
	{
	while (arr[i] != i) //depth of i array accesses
	i = arr[i];
	return i;
	}
	bool Find(int p, int q)
	{
	if (root(p) == root(q))//depth of p and q array accesses
	return true;
	return false;
	}
	void Union(int p, int q) //change the root of p to point to root q
	{
	int i = root(p);
	int j = root(q);
	arr[i] = j;
	}
	//2N+2 array access
	int size;
	};

view raw quickunion.cpp hosted with ❤ by GitHub