Find the number of disjoint sets
For those unfamiliar with the unbound set data structure.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
I am trying to find no. groups of friends from a given set of friends and their relationships. There is, of course, no doubt that this can be done easily with BFS / DFS. But I prefer to use a non-overlapping set, I also tend to find a group of friends that a person belongs to, etc., and of course an incompatible set of sounds is fine for this case.
I implemented the Disjoint set data structure.Now I need to find the number of disjoint sets it contains (which will give me the number of groups).
Now I am stuck with the implementation of how to efficiently find the number of disjoint sets, since the number of friends can be of size 1 00 00 0.
The options that I think should work.
-
Attach a new set at the end of the original and destroy the old set.
-
Change the parents of each element in each compound.
But since the number of friends is huge, I'm not sure if this is the right approach. Perhaps if there is any other efficient way or should I go ahead and implement any of the above.
Here is my code for more information. (I have not implemented counter-disjunct-set here)
//disjoint set concept
//https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/
// initially all the vertices are takes as single set and they are their own representative.
// next we see, compare two vertices, if they have same parent(representative of the set), we leave it.
// if they don't we merge them it one set.
// finally we get different disjoint sets.
#includes ...
using namespace std;
#define edge pair<int, int>
const int max 1000000;
vector<pair<int, edge > > graph, mst;
int N, M;
int parent[max];
int findset(int x, int* parent){
//find the set representative.
if(x != parent[x]){
parent[x] = findset(parent[x], parent);
}
return parent[x];
}
void disjoints(){
for(int i=0; i<M; i++){
int pu = findset(graph[i].second.first, parent);
int pv = findset(graph[i].second.second, parent);
if(pu != pv){ //if not in the same set.
mst.push_back(graph[i]);
total += graph[i].first;
parent[pu] = parent[pv]; // create the link between these two sets
}
}
}
void noOfDisjoints(){
//returns the No. of disjoint set.
}
void reset(){
for(int i=0; i<N; i++){
parent[i] = i;
}
}
int main() {
cin>>N>>M; // No. of friends and M edges
int u,v,w; // u= source, v= destination, w= weight(of no use here).
reset();
for(int i =0; i<M ;i++){
cin>>u>>v>>w;
graph.push_back(pair<int, edge>(w,edge(u,v)));
}
disjoints();
print();
return 0;
}
source to share
Each working operator on two elements a,b
in a data structure of unrelated sets has two possible scenarios:
- You tried to combine items from the same set. In this case, nothing is done, and the number of disjoint sets remains unchanged.
- You have merged elements from two different sets, so you basically converted the two sets into one - effectively reducing the number of disjoint sets to exactly one.
From this we can conclude that it is easy to find the number of disjoint sets at each moment by keeping track of the number of unions of type (2) from the above. If we denote this number by succ_unions
, then the total number of sets at each point will be number_of_initial_sets - succ_unions
.
source to share
If all you need to know is the number of non-overlapping sets, not what they are, one option is to add a counter variable to your data structure that counts how many non-overlapping sets there are. Initially there are n of them, one for each element. Every time you perform a union operation, if the two elements do not have the same representative, you know that you are combining two disjoint sets into one, so you can decrease the counter. It will look something like this:
if (pu != pv){ //if not in the same set.
numDisjointSets--; // <--- Add this line
mst.push_back(graph[i]);
total += graph[i].first;
parent[pu] = parent[pv]; // create the link between these two sets
}
Hope this helps!
source to share