Quick Find

This is a Quick Find algorithm

	//Union find
	//dynamic connectivity
	//reflexive: P is connected to P
	//symmetric: if p is connected to Q then Q is connected to P
	//transitive: if P is connected to Q and Q is connected to R then P is connected to R
	//connected components {0} {1 2 3}
	//Quick Find
	//eager algorithm
	//check if p and q have same id
	class QuickFind
	{
	int* arr;
	public:
	QuickFind(int num)
	{
	size = num;
	arr = new int[num];
	for (int i = 0; i < num; i++)
	arr[i] = i;
	}
	bool Find(int p, int q)
	{
	if (arr[p] == arr[q])
	return true;
	return false;
	}
	void Union(int p, int q)
	{
	int pid = arr[p];//1
	int qid = arr[q];//1
	for (int i = 0; i < size; i++)
	{
	if (arr[i] == qid)//N
	{
	arr[i] = pid;//N
	}
	}
	}
	//2N+2 array access
	int size;
	};

view raw QuickFind.cpp hosted with ❤ by GitHub