路径压缩并查集

#include<cstdio>

class UnionSet {
 private:
  int *father;
 public:
  UnionSet() : father(NULL) {  }
  UnionSet(int len) : father(NULL) {
    init(len);
  }
  void init(int len) {
    delete[] father;
    father = new int[len + 1];
    for(int i = 0; i <= len; ++i) {
      father[i] = i;
    }
  }
  int find(int son) {
    return son == father[son] ? son : father[son] = find(father[son]);
  }
  void join(int a, int b) {
    father[find(a)] = find(b);
  }
};

按秩合并并查集

#include<cstdio>

class UnionSet {
 private:
  int *father;
  int *depth;
 public:
  UnionSet() : father(NULL) {  }
  UnionSet(int len) : father(NULL) {
    init(len);
  }
  void init(int len) {
    delete[] father;
    father = new int[len + 1];
    delete[] depth;
    depth = new int[len + 1];
    for(int i = 0; i <= len; ++i) {
      father[i] = i;
      depth[i] = 0;
    }
  }
  int find(int son) {
    while(father[son] != son) son = father[son];
    return son;
  }
  void join(int a, int b) {
    a = find(a);
    b = find(b);
    if(depth[a] > depth[b]) std::swap(a, b);
    father[a] = b;
    if(depth[a] == depth[b]) ++depth[b];
    return;
  }
};

回滚并查集

#include<cstdio>
#include<stack>

class UnionSet {
 private:
  int *father;
  int *depth;
  std::stack<std::pair<int, int> > fatherc;
  std::stack<std::pair<int, int> > depthc;
 public:
  UnionSet() : father(NULL) {  }
  UnionSet(int len) : father(NULL) {
    init(len);
  }
  void init(int len) {
    delete[] father;
    father = new int[len + 1];
    delete[] depth;
    depth = new int[len + 1];
    while(!fatherc.empty()) fatherc.pop();
    while(!depthc.empty()) depthc.pop();
    for(int i = 0; i <= len; ++i) {
      father[i] = i;
      depth[i] = 0;
    }
  }
  int find(int son) {
    while(father[son] != son) son = father[son];
    return son;
  }
  void join(int a, int b) {
    a = find(a);
    b = find(b);
    if(depth[a] > depth[b]) std::swap(a, b);
    fatherc.push(std::make_pair(a, father[a]));
    father[a] = b;
    depthc.push(std::make_pair(b, depth[b]));//为了写起来方便，即使depth没被修改也记录一下 
    if(depth[a] == depth[b]) ++depth[b];
    return;
  }
  void undo() {
    father[fatherc.top().first] = fatherc.top().second;
    fatherc.pop();
    depth[depthc.top().first] = depthc.top().second;
    depthc.pop();
  }
};

可持久化并查集

//TODO