FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

Data-Structure-Algorithm/19Disjointsets.cpp at main · mayurgalhate/Data-Structure-Algorithm · GitHub

78 lines (68 loc) · 1.69 KB

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

66

67

68

69

70

71

72

73

74

75

76

77

78

#include <iostream>

using namespace std;

#include <vector>

class DisjointSet{

vector<int> rank, parent, size;

public:

DisjointSet(int n){

rank.resize(n+1, 0);

parent.resize(n+1);

size.resize(n+1);

for(int i = 0; i <= n; i++) {

parent[i] = i;

size[i] = 1;

}

}

int findUPar(int node) {

if(node == parent[node])

return node;

return parent[node] = findUPar(parent[node]);

}

void unionByRank(int u, int v) {

int ulp_u = findUPar(u);

int ulp_v = findUPar(v);

if(ulp_u == ulp_v) return;

if(rank[ulp_u] < rank[ulp_v]) {

parent[ulp_u] = ulp_v;

}

else if(rank[ulp_v] < rank[ulp_u]){

parent[ulp_v] = ulp_u;

}

else {

parent[ulp_v] = ulp_u;

rank[ulp_u]++;

}

}

void unionBySize(int u, int v) {

int ulp_u = findUPar(u);

int ulp_v = findUPar(v);

if(ulp_u == ulp_v) return;

if(size[ulp_u] < size[ulp_v]) {

parent[ulp_u] = ulp_v;

size[ulp_v] += size[ulp_u];

}

else {

parent[ulp_v] = ulp_u;

size[ulp_u] += size[ulp_v];

}

}

};

int main(){

DisjointSet ds(7);

ds.unionBySize(1, 2);

ds.unionBySize(2, 3);

ds.unionBySize(4, 5);

ds.unionBySize(6, 7);

ds.unionBySize(5, 6);

//if 3 and 7 same or not

if(ds.findUPar(3) == ds.findUPar(7)) {

cout << "Same" << endl;

}

else cout << "Not same\n";

ds.unionBySize(3, 7);

if(ds.findUPar(3) == ds.findUPar(7)) {

cout << "Same" << endl;

}

else cout << "Not same\n";

return 0;

}

Back | FazBrowse Home | New Git URL