二级考试C基础:并查集UFSet类

会计考友

　　/*
$ F9 T; G- o3 [: B! {5 b　　Name: 并查集UFSet类
  Y6 a0 G% m7 H$ A　　Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
) u2 c: i3 v% \# f+ I. v6 g　　Author: goal00001111
　　Date: 23-12-08 15:21
　　Description: 实现了普通的查找和合并的算法，也实现了压缩路径和按大小求并高效算法，并对两者进行了测试比较。
/ W) B8 }5 O5 i! D- A' N$ o　　有关算法的分析讨论详见拙作《一种简单而有趣的数据结构--并查集》：
' Z3 n3 U- V+ R: a* i　　*/
8 z- o+ b/ i5 g9 o4 T　　#include
0 C" y' B5 c2 b/ h3 ]: A. T; J　　#include
　　using namespace std;
　　const int MAX = 50000; //集合的最大成员数量
　　class UFSet{ //并查集类
( D$ P) u- Z3 a. U+ [- ?1 Q　　public:
+ R; D& J- Q) A7 K　　UFSet(int s = MAX); //构造函数
; R/ _0 R. G; ^- V/ y: j% [　　UFSet(const UFSet & obj); //拷贝构造函数
, L. c5 [( C" c) ~# b: D4 o+ V1 R" K　　~UFSet() //析构函数
　　{
　　delete []father;
+ H/ v' E/ L& g" \% Q+ Z/ l　　}
9 b# k; B: p; J, y; ^: w　　UFSet & operator = (const UFSet & obj); //赋值函数
9 I. P; F% ]1 t7 s( X  t) b* h　　int FindFather(int pos); //寻找序号pos的族长大人
/ A4 |, J: R& c/ |5 o- K, f% d1 ~　　bool Unite(int posI, int posJ);//将成员posI和posJ合并到同一个家族
　　int FindFatherAndReducePath(int pos); //查找族长并压缩路径
$ u- E2 T" l+ m& U6 F( C　　bool UnionBySize (int posI, int posJ); //按大小求并
　　bool SameFamily(int posI, int posJ); //判断成员posI和posJ是否属于同一家族
　　void PrintUFSet();
9 @7 {0 J, T+ W$ n　　private:
3 z! j" s& k" }# _6 ]% a" e* c: k　　int *father; //并查集成员数组，存放各元素的父亲结点
　　int size; //并查集成员数量
# V( w# i& A1 r4 v! @' F  v, K　　};
- V( q; a6 s8 ~　　UFSet::UFSet(int s) : size(s) //构造函数
; H1 c3 B, a9 a8 H3 ]　　{
　　father = new int[size + 1];
　　for (int i=0; i

会计考友

　　break;
0 O3 I9 J7 j- }　　}
　　time(&endTime);
　　cout