qunionfind.cpp

来自「算断裂的」· C++ 代码 · 共 103 行

// ------------------------------------------------------------------
// qunionfind.cpp
//
// This file contains member functions for doing a union-find
// computation on a set of integers 0...n-1.  Does union-find
// in O(n log n).
// ------------------------------------------------------------------
// Author: Stephen A. Vavasis
// Copyright (c) 1999 by Cornell University.  All rights reserved.
// 
// See the accompanying file 'Copyright' for authorship information,
// the terms of the license governing this software, and disclaimers
// concerning this software.
// ------------------------------------------------------------------
// This file is part of the QMG software.  
// Version 2.0 of QMG, release date September 3, 1999.
// ------------------------------------------------------------------

#include "qunionfind.h"


void QMG::UnionFind::initialize(int sz)  {
  parent_.resize(sz);
  rename_label_.resize(sz);
  inv_rename_label_.resize(sz);
  lsize_.resize(sz);
  size_ = sz;
  for (int k = 0; k < sz; ++k) {
    parent_[k] = k;
    rename_label_[k] = k;
    inv_rename_label_[k] = k;
    lsize_[k] = 1;
  }
}

void QMG::UnionFind::merge(int i1, int i2) {
  int c1 = get_label_unrenamed_(i1);
  int c2 = get_label_unrenamed_(i2);
  if (c1 == c2)
    return;
  int largerc, smallerc;
  if (lsize_[c1] >= lsize_[c2]) {
    largerc = c1;
    smallerc = c2;
  }
  else {
    largerc = c2;
    smallerc = c1;
  }
  parent_[smallerc] = largerc;
  lsize_[largerc] += lsize_[smallerc];
  lsize_[smallerc] = 0;
}

int QMG::UnionFind::get_label_unrenamed_(int i0) const {
  int i1 = i0;
  tmplist_.resize(1,i1);
  int p = parent_[i1];
  while (p != i1) {
    tmplist_.push_back(p);
    i1 = p;
    p = parent_[i1];
  }
  while (tmplist_.size()) {
    parent_[tmplist_.back()] = p;
    tmplist_.pop_back();
  }
  return p;
}

int QMG::UnionFind::get_label(int i1) const {
  return rename_label_[get_label_unrenamed_(i1)];
}


#ifndef BUG_IN_USING
using QMG::vector;
#endif

const vector<int>& QMG::UnionFind::retrieve_labels() const {
  labels_.resize(size_);
  for (int i = 0; i < size_; ++i)
    labels_[i] = get_label(i);
  return labels_;
}

  
int QMG::UnionFind::pack_labels() {
  int newlab = 0;
  for (int i = 0; i < size_; ++i) {
    if (lsize_[i]) {
      inv_rename_label_[newlab] = i;
      rename_label_[i] = newlab++;
    }
  }
  return newlab;
}

int QMG::UnionFind::label_size(int i) const {
  return lsize_[inv_rename_label_[i]];
}