并查集

并查集的以下几种优化和类型。

1.路径压缩

 1 int pre[maxv];
 2 void init(int n)
 3 {
 4     /*初始化w*/
 5     for (int i= 0; i<= n; i ++) pre[i]= i;
 6 }
 7 int findFa(int x)
 8 {
 9     /*寻找树的根节点，并路径压缩w*/
10     if (pre[x]== x) return x;
11     return pre[x]= findFa(pre[x]);
12 }
13 void join(int x, int y)
14 {
15     /*把x 所在的树并在y 所在的树的根节点下w*/
16     pre[findFa(x)]= findFa(y);
17 }

2.按秩合并

 1 int pre[maxv];
 2 int _rank[maxv];
 3 void init(int n)
 4 {
 5     for (int i= 0; i<= n; i ++) pre[i]= i;
 6     for (int i= 0; i<= n; i ++) _rank[i]= 1;
 7 }
 8 int findFa(int x)
 9 {
10     /*寻找树的根节点，并路径压缩w*/
11     if (pre[x]== x) return x;
12     return pre[x]= findFa(pre[x]);
13 }
14 void join(int x, int y)
15 {
16     /*按秩合并，秩为树的大小*/
17     int fx= findFa(x);
18     int fy= findFa(y);
19     if (_rank[fx]> _rank[fy])
20     {
21         pre[fy]= fx;
22         _rank[fx]= _rank[fx]+ _rank[fy];
23     }
24     else
25     {
26         pre[fx]= fy;
27         _rank[fy]= _rank[fy]+ _rank[fx];
28     }
29 }

 1 int pre[maxv];
 2 int _rank[maxv];
 3 void init(int n)
 4 {
 5     for (int i= 0; i<= n; i ++) pre[i]= i;
 6     for (int i= 0; i<= n; i ++) _rank[i]= 1;
 7 }
 8 int findFa(int x)
 9 {
10     /*寻找树的根节点，并路径压缩w*/
11     if (pre[x]== x) return x;
12     return pre[x]= findFa(pre[x]);
13 }
14 void join(int x, int y)
15 {
16     /*按秩合并，秩为树的高*/
17     /*ps: 有路径压缩感觉这个没什么用*/
18     int fx= findFa(x);
19     int fy= findFa(y);
20     if (_rank[fx]> _rank[fy])
21     {
22         pre[fy]= fx;
23         _rank[fx]= min(_rank[fx], _rank[fy]+ 1);
24     }
25     else
26     {
27         pre[fx]= fy;
28         _rank[fy]= min(_rank[fy], _rank[fx]+ 1);
29     }
30 }

end；