Algorithm-DS-Problems/disjoint_set_data_structure.cpp at master · ankishb/Algorithm-DS-Problems · GitHub

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <bits/stdc++.h>
using namespace std;

class DisjointSet{
	int *rank;
	int parent;
	int n;

public:
	DisjointSet(int n){
		rank = new int[n];
		parent = new int[n];
		this->n = n;
		makeset();
	}

	void makeset(){
		for(int i=0; i<n; i++){
			parent[i] = i;
		}
	}

	void find(int x){
		if(parent[x] != x){
			parent[x] = find(parent[x])
		}
		return parent[x];
	}

	void union(int x, int y){
		int x_set = find(x);
		int y_set = find(y);
		// if both element belong to same set
		if(x_set == y_set){
			return ;
		}
		// find rank of them, take union according
		// 1. Choose parent to that set, which have higher rank
		// 2. If rank equal, run path compression algo
		if(rank[x_set] < rank[y_set]){
			parent[x_set] = y_set;
		}
		else if(rank[x_set] > rank[y_set]){
			parent[y_set] = x_set;
		}
		else{
			parent[y_set] = x_set;
			rank[x_set] = rank[x_set]+1;
		}
	}
}

int main()
{
	DisjointSet set(5);
	set.union(0, 2);
	set.union(4, 2);
	set.union(3, 1);

}


class DisjointSet{
	vector<int> rank;
	vector<int> parent;
	int n;

public:
	DisjointSet(int n_){
		vector<int> temp(n_, 0);
		rank = temp;
		parent = temp;
		n = n_;
		makeset();
	}

	void makeset(){
		for(int i=0; i<n; i++){
			parent[i] = i;
		}
	}

	void print_parent(){
        for(auto itr : parent) cout<<itr<<" ";
		cout<<endl;
	}

	void find(int x){
		if(parent[x] != x){
			parent[x] = find(parent[x])
		}
		return parent[x];
	}

	void union_(int x, int y){
		int x_set = find(x);
		int y_set = find(y);
		// if both element belong to same set
		if(x_set == y_set){
			return ;
		}
		// find rank of them, take union according
		// 1. Choose parent to that set, which have higher rank
		// 2. If rank equal, run path compression algo
		if(rank[x_set] < rank[y_set]){
			parent[x_set] = y_set;
		}
		else if(rank[x_set] > rank[y_set]){
			parent[y_set] = x_set;
		}
		else{
			parent[y_set] = x_set;
			rank[x_set] = rank[x_set]+1;
		}
	}
};