UnionFindTestHelper.h
#ifndef INC_02_QUICK_FIND_UNIONFINDTESTHELPER_H
#define INC_02_QUICK_FIND_UNIONFINDTESTHELPER_H
#include <iostream>
#include <ctime>
#include "UnionFind1.h"
using namespace std;
namespace UnionFindTestHelper{
void testUF1( int n ){
srand( time(NULL) );
UF1::UnionFind uf = UF1::UnionFind(n);
time_t startTime = clock();
for( int i = 0 ; i < n ; i ++ ){
int a = rand()%n;
int b = rand()%n;
uf.unionElements(a,b);
}
for(int i = 0 ; i < n ; i ++ ){
int a = rand()%n;
int b = rand()%n;
uf.isConnected(a,b);
}
time_t endTime = clock();
cout<<"UF1, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
}
}
#endif
UnionFind.h
#ifndef INC_02_QUICK_FIND_UNIONFIND1_H
#define INC_02_QUICK_FIND_UNIONFIND1_H
#include <iostream>
#include <cassert>
using namespace std;
namespace UF1 {
class UnionFind {
private:
int *id;
int count;
public:
UnionFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
~UnionFind() {
delete[] id;
}
int find(int p) {
assert(p >= 0 && p < count);
return id[p];
}
bool isConnected(int p, int q) {
return find(p) == find(q);
}
void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
};
}
#endif
main.cpp
#include <iostream>
#include "UnionFindTestHelper.h"
using namespace std;
int main() {
int n = 10000;
UnionFindTestHelper::testUF1(n);
return 0;
}