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

Question

Для тех, кто не знаком с структурой данных с несвязанными наборами.

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

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

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

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

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

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

2. Смена родителей каждого элемента в каждом профсоюзе.

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

Вот мой код для получения дополнительной информации. (I'have не реализован подсчет непересекающегося-ния здесь)

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

Answer 1

Каждый союз по двум Отделом пунктов a,b в структуре Disjoint Набор данных имеет два возможных сценария:

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

Из этого можно сделать вывод, что легко найти число непересекающихся множеств в каждый момент, отслеживая количество объединений типа (2) из ​​приведенного выше.
Если обозначить это число на succ_unions, то общее количество наборов в каждой точке равно number_of_initial_sets - succ_unions.

Answer 2

Если все, что вам нужно знать, это числа непересекающихся множества, а не то, что они есть один вариант - добавить в счетную переменную в свою структуру данных, подсчитывая, сколько там непересекающихся наборов. Первоначально, n из них, по одному на отдельный элемент. Каждый раз, когда вы выполняете операцию объединения, если два элемента не имеют одного и того же представителя, то вы знаете, что вы объединяете два непересекающихся множества в один, чтобы вы могли уменьшить счетчик. Это будет выглядеть примерно так:

if (pu != pv){ //if not in the same set. 
    numDisjointSets--; // <--- Add thie line 
    mst.push_back(graph[i]); 
    total += graph[i].first; 
    parent[pu] = parent[pv]; // create the link between these two sets 
} 

Надеюсь, это поможет!