Найти количество непересекающихся множеств

Для тех, кто не знаком со структурой данных Disjoint-set.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Я пытаюсь найти нет. групп друзей из заданных наборов друзей и их отношений. Конечно, нет сомнений в том, что это можно легко реализовать с помощью BFS / DFS. Но я предпочитаю использовать непересекающийся набор, я также склонен находить группу друзей, к которой принадлежит человек, и т. Д., И непересекающийся набор, безусловно, подходит для этого случая.

Я реализовал структуру данных о непересекающихся наборах. Теперь мне нужно найти количество содержащихся в нем непересекающихся наборов (что даст мне количество групп).

Теперь я застрял в реализации того, как эффективно найти количество непересекающихся множеств, так как количество друзей может достигать 1 00 00 0.

Варианты, которые я думаю, должны работать.

1. Прикрепите новый набор сзади оригинала и уничтожьте старый.

2. Меняйте своих родителей каждого элемента в каждом союзе.

Но так как количество друзей огромно, я не уверен, что это правильный подход, возможно, если есть какой-либо другой эффективный способ, или я должен идти вперед и реализовать любой из вышеперечисленных.

Вот мой код для дополнительных деталей. (Я не реализовал подсчет-дизъюнкт-набор здесь)

//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;
}