C++ 并查集 高级数据结构_c ++实现并查集问题的方法并且比较用各个数据结构解决并查集问题的优缺点

并查集(Union Find)，又称不相交集合(Disjoint Set)，它应用于N个元素的集合求并与查询问题，在该应用场景中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。虽然该问题并不复杂，但面对极大的数据量时，普通的数据结构往往无法解决，并查集就是解决该种问题最优秀的算法。

#include<vector>
class DisjointSet
{
public:
 DisjointSet(int n) 
 {
  for (int i = 0; i < n; i++)
  {
   _id.push_back(i);
  }
 }
 int find(int p)
 {
  return _id[p];
 }
 void Union(int p, int q)
 {
  int pid = find(p);
  int qid = find(q);
  if (pid==qid)
  {
   return;
  }
  for (int i = 0; i < _id.size(); i++)
  {
   if (_id[i]==pid)
   {
    _id[i] = qid;
   }
  }
 }
 void print_set()
 {
  printf("元素:  ");
  for (int i = 0; i < _id.size(); i++)
  {
   printf("%d  ",i);
  }
  printf("\n");
  printf("集合:  ");
  for (int i = 0; i < _id.size(); i++)
  {
   printf("%d  ",_id[i]);
  }
  printf("\n");
 }
private:
 std::vector<int> _id;
};
int main()
{
 DisjointSet disjoint_set(8);
 disjoint_set.print_set();
 printf("Union(0, 5)\n");
 disjoint_set.Union(0, 5);
 disjoint_set.print_set();
 printf("Find(0)==%d, Find(5)=%d\n", disjoint_set.find(0), disjoint_set.find(5));
 printf("Find(2)==%d, Find(5)=%d\n", disjoint_set.find(2), disjoint_set.find(5));
 disjoint_set.Union(2, 4);
 disjoint_set.print_set();
 disjoint_set.Union(0, 4);
 disjoint_set.print_set();
 printf("Find(2)==%d, Find(5)=%d\n", disjoint_set.find(2), disjoint_set.find(5));
 return 0;
}
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
64

运行结果为:

元素:  0  1  2  3  4  5  6  7
集合:  0  1  2  3  4  5  6  7
Union(0, 5)
元素:  0  1  2  3  4  5  6  7
集合:  5  1  2  3  4  5  6  7
Find(0)==5, Find(5)=5
Find(2)==2, Find(5)=5
元素:  0  1  2  3  4  5  6  7
集合:  5  1  4  3  4  5  6  7
元素:  0  1  2  3  4  5  6  7
集合:  4  1  4  3  4  4  6  7
Find(2)==4, Find(5)=4
1
2
3
4
5
6
7
8
9
10
11