######01版本的并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<iostream>
using namespace std;
class UF{
private:
int *id;
int size;
int *num;
public:
UF(int n){
id=new int [n];
num=new int [n];
this->size=n;
for(int i=0;i<n;i++){
id[i]=i;
num[i]=1;
}
}
//得到一共有多少个元素
int getSize(){
return size;
}
//查询
int Find(int p){
if(p<0||p>=size){
cout<<"Error"<<endl;
return NULL;
}
if(p==id[p])
return p;
else{
return Find(id[p]);
}
}
//判断两个值是否连接
bool isConnected(int p,int q){
return Find(p)==Find(q);
}
//给两个数并在一起
void unionelem(int p,int q){
int PID=Find(p);
int QID=Find(q);
if(PID==QID)
return ;
//看谁的元素多，把元素多的作为根
if(num[PID]<num[QID]){
id[PID]=QID;
num[QID]+=num[PID];
}else{
id[QID]=PID;
num[PID]+=num[QID];
}
}
};
int main()
{
return 0;
}
|
######02版本的并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<iostream>
using namespace std;
class UF{
private:
int *id;
int size;
int *rank;
public:
UF(int n){
id=new int [n];
rank=new int [n];
this->size=n;
for(int i=0;i<n;i++){
id[i]=i;
rank[i]=1;
}
}
//得到一共有多少个元素
int getSize(){
return size;
}
//查询
int Find(int p){
if(p<0||p>=size){
cout<<"Error"<<endl;
return NULL;
}
if(p==id[p])
return p;
else{
return Find(id[p]);
}
}
//判断两个值是否连接
bool isConnected(int p,int q){
return Find(p)==Find(q);
}
//给两个数并在一起
void unionelem(int p,int q){
int PID=Find(p);
int QID=Find(q);
if(PID==QID)
return ;
if(rank[PID]<rank[QID]){
id[PID]=QID;
}
else if(rank[QID]<rank[PID]){
id[QID]=PID;
}
else {
id[PID]=QID;
rank[QID]+=1;
}
}
};
int main()
{
return 0;
}
|
其中，Find()函数还可以进行路径压缩优化:
1
2
3
4
5
6
7
8
9
10
11
| int find(int p)
{
// while(p!=parent[p]) {
// parent[p]=parent[parent[p]]; //path Compression(路径压缩)
// p = parent[p];
// }
// return p;
if(p!=parent[p])
parent[p]=find(parent[p]);
return parent[p];
}
|
-
Next Post
线段树
-
Previous Post
