Quick Find Algorithm and DataStructure

qfind.cpp

#include <iostream>

template<int N>
class quick_find{
public:
	quick_find()
	{
		for(int i =0; i < N; ++i){
			elements[i] = i;
		}
	}

	bool connected(int p, int q) const{
		return (elements[p] == elements[q]); // are they in the same connected component?
	}

	void union_components(int p, int q){
		auto pvalue = elements[p];
		auto qvalue = elements[q];
		for(int i =0; i < N; ++i)
		{
			if(elements[i] == qvalue)
				elements[i] = pvalue;
		}
	}

private:
	int elements[N];
};

int main(){

	quick_find<10> q;

	q.union_components(0,1);
	q.union_components(1,2);

	using namespace std;

	cout << "Connected: " << boolalpha << (q.connected(0,1)) << endl;
	cout << "Connected: " << boolalpha << (q.connected(1,2)) << endl;
	cout << "Connected: " << boolalpha << (q.connected(2,2)) << endl;
	cout << "Connected: " << boolalpha << (q.connected(0,8)) << endl;

	return 0;
}