Skip to content

Commit 46bae3a

Browse files
liuyuboboboliuyubobobo
committed
Chapter 06 added a new optional case. To test our UFs performance, we try to use the same test cases:)
1 parent 651f7b3 commit 46bae3a

File tree

8 files changed

+616
-0
lines changed

8 files changed

+616
-0
lines changed

‎06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/CMakeLists.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
cmake_minimum_required(VERSION 3.5)
2+
project(Optional_01_Same_Cases_Test_for_UF)
3+
4+
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
5+
6+
set(SOURCE_FILES main.cpp)
7+
add_executable(Optional_01_Same_Cases_Test_for_UF ${SOURCE_FILES})

‎06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind1.h

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
//
2+
// Created by liuyubobobo on 5/5/17.
3+
//
4+
5+
#ifndef INC_06_PATH_COMPRESSION_UNIONFIND1_H
6+
#define INC_06_PATH_COMPRESSION_UNIONFIND1_H
7+
8+
#include <iostream>
9+
#include <cassert>
10+
11+
using namespace std;
12+
13+
// 我们的第一版Union-Find
14+
namespace UF1 {
15+
16+
class UnionFind {
17+
18+
private:
19+
int *id; // 我们的第一版Union-Find本质就是一个数组
20+
int count; // 数据个数
21+
22+
public:
23+
// 构造函数
24+
UnionFind(int n) {
25+
count = n;
26+
id = new int[n];
27+
// 初始化, 每一个id[i]指向自己, 没有合并的元素
28+
for (int i = 0; i < n; i++)
29+
id[i] = i;
30+
}
31+
32+
// 析构函数
33+
~UnionFind() {
34+
delete[] id;
35+
}
36+
37+
// 查找过程, 查找元素p所对应的集合编号
38+
int find(int p) {
39+
assert(p >= 0 && p < count);
40+
return id[p];
41+
}
42+
43+
// 查看元素p和元素q是否所属一个集合
44+
// O(1)复杂度
45+
bool isConnected(int p, int q) {
46+
return find(p) == find(q);
47+
}
48+
49+
// 合并元素p和元素q所属的集合
50+
// O(n) 复杂度
51+
void unionElements(int p, int q) {
52+
53+
int pID = find(p);
54+
int qID = find(q);
55+
56+
if (pID == qID)
57+
return;
58+
59+
// 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
60+
for (int i = 0; i < count; i++)
61+
if (id[i] == pID)
62+
id[i] = qID;
63+
}
64+
};
65+
}
66+
67+
#endif //INC_06_PATH_COMPRESSION_UNIONFIND1_H

‎06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind2.h

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
//
2+
// Created by liuyubobobo on 5/5/17.
3+
//
4+
5+
#ifndef INC_06_PATH_COMPRESSION_UNIONFIND2_H
6+
#define INC_06_PATH_COMPRESSION_UNIONFIND2_H
7+
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
// 我们的第二版Union-Find
13+
namespace UF2{
14+
15+
class UnionFind{
16+
17+
private:
18+
// 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
19+
// parent[i]表示第一个元素所指向的父节点
20+
int* parent;
21+
int count; // 数据个数
22+
23+
public:
24+
// 构造函数
25+
UnionFind(int count){
26+
parent = new int[count];
27+
this->count = count;
28+
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
29+
for( int i = 0 ; i < count ; i ++ )
30+
parent[i] = i;
31+
}
32+
33+
// 析构函数
34+
~UnionFind(){
35+
delete[] parent;
36+
}
37+
38+
// 查找过程, 查找元素p所对应的集合编号
39+
int find(int p){
40+
assert( p >= 0 && p < count );
41+
// 不断去查询自己的父亲节点, 直到到达根节点
42+
// 根节点的特点: parent[p] == p
43+
while( p != parent[p] )
44+
p = parent[p];
45+
return p;
46+
}
47+
48+
// 查看元素p和元素q是否所属一个集合
49+
// O(h)复杂度, h为树的高度
50+
bool isConnected( int p , int q ){
51+
return find(p) == find(q);
52+
}
53+
54+
// 合并元素p和元素q所属的集合
55+
// O(h)复杂度, h为树的高度
56+
void unionElements(int p, int q){
57+
58+
int pRoot = find(p);
59+
int qRoot = find(q);
60+
61+
if( pRoot == qRoot )
62+
return;
63+
64+
parent[pRoot] = qRoot;
65+
}
66+
};
67+
}
68+
69+
#endif //INC_06_PATH_COMPRESSION_UNIONFIND2_H

‎06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind3.h

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
//
2+
// Created by liuyubobobo on 5/5/17.
3+
//
4+
5+
#ifndef INC_06_PATH_COMPRESSION_UNIONFIND3_H
6+
#define INC_06_PATH_COMPRESSION_UNIONFIND3_H
7+
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
// 我们的第三版Union-Find
13+
namespace UF3{
14+
15+
class UnionFind{
16+
17+
private:
18+
int* parent; // parent[i]表示第i个元素所指向的父节点
19+
int* sz; // sz[i]表示以i为根的集合中元素个数
20+
int count; // 数据个数
21+
22+
public:
23+
// 构造函数
24+
UnionFind(int count){
25+
parent = new int[count];
26+
sz = new int[count];
27+
this->count = count;
28+
for( int i = 0 ; i < count ; i ++ ){
29+
parent[i] = i;
30+
sz[i] = 1;
31+
}
32+
}
33+
34+
// 析构函数
35+
~UnionFind(){
36+
delete[] parent;
37+
delete[] sz;
38+
}
39+
40+
// 查找过程, 查找元素p所对应的集合编号
41+
// O(h)复杂度, h为树的高度
42+
int find(int p){
43+
assert( p >= 0 && p < count );
44+
// 不断去查询自己的父亲节点, 直到到达根节点
45+
// 根节点的特点: parent[p] == p
46+
while( p != parent[p] )
47+
p = parent[p];
48+
return p;
49+
}
50+
51+
// 查看元素p和元素q是否所属一个集合
52+
// O(h)复杂度, h为树的高度
53+
bool isConnected( int p , int q ){
54+
return find(p) == find(q);
55+
}
56+
57+
// 合并元素p和元素q所属的集合
58+
// O(h)复杂度, h为树的高度
59+
void unionElements(int p, int q){
60+
61+
int pRoot = find(p);
62+
int qRoot = find(q);
63+
64+
if( pRoot == qRoot )
65+
return;
66+
67+
// 根据两个元素所在树的元素个数不同判断合并方向
68+
// 将元素个数少的集合合并到元素个数多的集合上
69+
if( sz[pRoot] < sz[qRoot] ){
70+
parent[pRoot] = qRoot;
71+
sz[qRoot] += sz[pRoot];
72+
}
73+
else{
74+
parent[qRoot] = pRoot;
75+
sz[pRoot] += sz[qRoot];
76+
}
77+
}
78+
};
79+
}
80+
81+
#endif //INC_06_PATH_COMPRESSION_UNIONFIND3_H

‎06-Union-Find/Course Code (C++)/Optional-01-Same-Cases-Test-for-UF/UnionFind4.h

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
//
2+
// Created by liuyubobobo on 5/5/17.
3+
//
4+
5+
#ifndef INC_06_PATH_COMPRESSION_UNIONFIND4_H
6+
#define INC_06_PATH_COMPRESSION_UNIONFIND4_H
7+
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
// 我们的第四版Union-Find
13+
namespace UF4{
14+
15+
class UnionFind{
16+
17+
private:
18+
int* rank; // rank[i]表示以i为根的集合所表示的树的层数
19+
int* parent; // parent[i]表示第i个元素所指向的父节点
20+
int count; // 数据个数
21+
22+
public:
23+
// 构造函数
24+
UnionFind(int count){
25+
parent = new int[count];
26+
rank = new int[count];
27+
this->count = count;
28+
for( int i = 0 ; i < count ; i ++ ){
29+
parent[i] = i;
30+
rank[i] = 1;
31+
}
32+
}
33+
34+
// 析构函数
35+
~UnionFind(){
36+
delete[] parent;
37+
delete[] rank;
38+
}
39+
40+
// 查找过程, 查找元素p所对应的集合编号
41+
// O(h)复杂度, h为树的高度
42+
int find(int p){
43+
assert( p >= 0 && p < count );
44+
// 不断去查询自己的父亲节点, 直到到达根节点
45+
// 根节点的特点: parent[p] == p
46+
while( p != parent[p] )
47+
p = parent[p];
48+
return p;
49+
}
50+
51+
// 查看元素p和元素q是否所属一个集合
52+
// O(h)复杂度, h为树的高度
53+
bool isConnected( int p , int q ){
54+
return find(p) == find(q);
55+
}
56+
57+
// 合并元素p和元素q所属的集合
58+
// O(h)复杂度, h为树的高度
59+
void unionElements(int p, int q){
60+
61+
int pRoot = find(p);
62+
int qRoot = find(q);
63+
64+
if( pRoot == qRoot )
65+
return;
66+
67+
// 根据两个元素所在树的元素个数不同判断合并方向
68+
// 将元素个数少的集合合并到元素个数多的集合上
69+
if( rank[pRoot] < rank[qRoot] ){
70+
parent[pRoot] = qRoot;
71+
}
72+
else if( rank[qRoot] < rank[pRoot]){
73+
parent[qRoot] = pRoot;
74+
}
75+
else{ // rank[pRoot] == rank[qRoot]
76+
parent[pRoot] = qRoot;
77+
rank[qRoot] += 1; // 此时, 我维护rank的值
78+
}
79+
}
80+
};
81+
}
82+
83+
#endif //INC_06_PATH_COMPRESSION_UNIONFIND4_H

0 commit comments

Comments
 (0)