00001 #ifndef DISJOINT_SET
00002 #define DISJOINT_SET
00003
00004
00005
00006 typedef struct {
00007 int rank;
00008 int p;
00009 int size;
00010 } uni_elt;
00011
00012 class universe {
00013 public:
00014 universe(int elements);
00015 ~universe();
00016 int find(int x);
00017 void join(int x, int y);
00018 int size(int x) const { return elts[x].size; }
00019 int num_sets() const { return num; }
00020
00021 private:
00022 uni_elt *elts;
00023 int num;
00024 };
00025
00026 universe::universe(int elements) {
00027 elts = new uni_elt[elements];
00028 num = elements;
00029 for (int i = 0; i < elements; i++) {
00030 elts[i].rank = 0;
00031 elts[i].size = 1;
00032 elts[i].p = i;
00033 }
00034 }
00035
00036 universe::~universe() {
00037 delete [] elts;
00038 }
00039
00040 int universe::find(int x) {
00041 int y = x;
00042 while (y != elts[y].p)
00043 y = elts[y].p;
00044 elts[x].p = y;
00045 return y;
00046 }
00047
00048 void universe::join(int x, int y) {
00049 if (elts[x].rank > elts[y].rank) {
00050 elts[y].p = x;
00051 elts[x].size += elts[y].size;
00052 } else {
00053 elts[x].p = y;
00054 elts[y].size += elts[x].size;
00055 if (elts[x].rank == elts[y].rank)
00056 elts[y].rank++;
00057 }
00058 num--;
00059 }
00060
00061 #endif