-
Notifications
You must be signed in to change notification settings - Fork 1
/
unionFindFabhoModified.cpp
133 lines (116 loc) · 2.79 KB
/
unionFindFabhoModified.cpp
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <cstdio>
#define ELEMENTS 1000
using namespace std;
int parent[ELEMENTS];//points to its parent or its representative of its set
int rank[ELEMENTS];
int numDisjointSets;
//for faster implementation and less function calls we don't call make set
//n times we only call make sets 1 time.
void make_sets(int number_of_elements)
{
numDisjointSets = number_of_elements;
int i;
for(i = 0; i < number_of_elements; i++)
{
parent[i] = i;
rank[i] = 1;
}
}
int find_set(int element)
{
if(element != parent[element])
parent[element] = find_set(parent[element]);
return parent[element];
}
bool isSameSet(int i, int j)
{
return find_set(i) == find_set(j);
}
void set_union(int x, int y)//where x and y are elements of different sets
{
int rx, ry; //roots or representatives of x and y sets
rx = find_set(x);
ry = find_set(y);
if(rx == ry) // it means the elements already are in the same set
return;
numDisjointSets--;
if(rank[rx] > rank[ry])
{
rank[rx] += rank[ry];
parent[ry] = rx;
}
else
{
rank[ry] += rank[rx];
parent[rx] = ry;
}
//rank[ry] += rank[rx];
//parent[rx] = ry;
}
int getNumSets()
{
return numDisjointSets;
}
int sizeOfSet(int i)
{
return rank[find_set(i)];
}
int main()
{
int number_of_elements;
int s1, s2;
int unions;
int finds;
int i,j;
int sizes;
scanf("%d", &number_of_elements);
make_sets(number_of_elements);
//perform any of the required set operations.
cout<<"initial sets"<<endl;
for(i = 0; i < number_of_elements; i++)
cout<<parent[i]<<" ";
cout<<endl;
cout<<"initial ranks"<<endl;
for(i = 0; i < number_of_elements; i++)
cout<<rank[i]<<" ";
cout<<endl;
//some operations
//unions
scanf("%d", &unions);
for(i = 0; i < unions; i++)
{
scanf("%d %d", &s1, &s2);
set_union(s1,s2);
cout<<"sets: ";
for(j = 0; j < number_of_elements; j++)
cout<<parent[j]<<" ";
cout<<endl;
cout<<"ranks: ";
for(j = 0; j < number_of_elements; j++)
cout<<rank[j]<<" ";
cout<<endl;
}
//finds
scanf("%d", &finds);
for(i = 0; i < finds; i++)
{
scanf("%d", &s1);
cout<<s1<<" belongs to the set: "<<find_set(s1)<<endl;
for(j = 0; j < number_of_elements; j++)
cout<<parent[j]<<" ";
cout<<endl;
for(j = 0; j < number_of_elements; j++)
cout<<rank[j]<<" ";
cout<<endl;
}
int setSize;
cout<<"Finding size\n";
cin>>sizes;
for(i = 0; i < sizes; i++)
{
scanf("%d", &setSize);
cout<<setSize<<" size is: "<<sizeOfSet(setSize)<<endl;
}
return 0;
}