uf.cpp

经典c++程序的实现

#include <iostream.h>
#include "book.h"

// Collect together the UNION/FIND functions
#include "uf.h"

Gentree::Gentree(int sz) {     // Constructor
  size = sz;
  array = new GTNode[sz];      // Create node array
}

Gentree::~Gentree() {          // Destructor
  delete [] array;             // Free node array
}

bool Gentree::differ(int a, int b) { // Nodes in different trees?
  GTNode* root1 = FIND(&array[a]);   // Find root of node a
  GTNode* root2 = FIND(&array[b]);   // Find root of node b
  return root1 != root2;             // Compare roots
}

void Gentree::UNION(int a, int b) {  // Merge two subtrees
  GTNode* root1 = FIND(&array[a]);   // Find root of node a
  GTNode* root2 = FIND(&array[b]);   // Find root of node b
  if (root1 != root2) root2->par = root1; // Merge subtrees
}

GTNode* Gentree::FIND(GTNode* curr) const {
  if (curr->parent() == NULL) return curr;  // At root
    return curr->par = FIND(curr->parent());
}