C++实现并查集

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

#include <iostream>

#include <vector>

#include <cassert>

usingnamespacestd;

classUnionFind{

private:

vector<int> parent;

intcount;

//优化，记录p和q所在组的深度，在合并时将深度小的结点的根指向深度大的结点的根

vector<int> rank;

public:

UnionFind(intcount){

parent.resize(count);

rank.resize(count);

this->count = count;

for(inti = 0; i < count; ++i){

parent[i] = i;

rank[i] = 1;

}

}

~UnionFind(){

parent.clear();

rank.clear();

}

//路径压缩

intfind(intp){

assert(p >= 0 && p < count);

if(p != parent[p])

parent[p] = find(parent[p]);

returnparent[p];

}

boolisConnected(intp,intq){

returnfind(p) == find(q);

}

voidunionElement(intp,intq){

intpRoot = find(p), qRoot = find(q);

if(pRoot == qRoot)

return;

if(rank[pRoot] < rank[qRoot])

parent[pRoot] = qRoot;

elseif(rank[qRoot] < rank[pRoot])

parent[qRoot] = pRoot;

else{

//两者的rank相等

parent[pRoot] = qRoot;

rank[qRoot] += 1;

}

}

};

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

65

#include <iostream>

usingnamespacestd;

classUF {

//cnt is the number of disjoint sets.

//id is an array that records distinct identity of each set,when two sets are merged ,their id will be same.

//sz is an array that records the child number of each set including the set self.

int*id, cnt, *sz;

public:

// Create an empty union find data structure with N isolated sets.

UF(intN) {

cnt = N;

id =newint[N];

sz =newint[N];

for(inti = 0; i<N; i++) {

id[i] = i;

sz[i] = 1;

}

}

~UF() {

delete[] id;

delete[] sz;

}

// Return the id of component corresponding to object p.

intfind(intp) {

if(p != id[p]){

id[p] = find(id[p]);

}

returnid[p];

}

// Replace sets containing x and y with their union.

voidmerge(intx,inty) {

inti = find(x);

intj = find(y);

if(i == j)return;

// make smaller root point to larger one

if(sz[i] < sz[j]) {

id[i] = j;

sz[j] += sz[i];

}

else{

id[j] = i;

sz[i] += sz[j];

}

cnt--;

}

// Are objects x and y in the same set?

boolconnected(intx,inty) {

returnfind(x) == find(y);

}

// Return the number of disjoint sets.

intcount() {

returncnt;

}

};

voidmain(){

UF test(5);

test.merge(2, 3);

test.merge(3, 4);

cout << test.find(4);

cout << test.count();

}