查找不相交集合的数量

对于不熟悉不相交集合数据结构的人员。查找不相交集合的数量

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

我试图找到没有。来自特定朋友的朋友群体及其关系。当然，毫无疑问，这可以使用BFS/DFS轻松实现。但是我选择使用不相交集合，我也倾向于找到该人属于的朋友组等等，并且在这种情况下，脱节设置听起来是合适的。

我已经实现了不相交集数据结构，现在我需要找到它包含的不相交集的数目（这会给我组的数量）。

现在，我被困在执行上如何有效地找到相交集合的号，作为朋友的数量可以大到1 00 00 0

选项，我认为应该工作。

将新套装附在原件的后面，销毁旧套件。
更改他们在每个工会的每个元素的父母。

但由于朋友的数量是巨大的，我不知道这是正确的做法，也许，如果有任何其他有效的方式还是应该继续和实施上述任何。

这里是我的其他详细信息的代码。（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; 
}

来源

2015-06-17 nitte93user3232918

在分离集数据结构上的两个项目a,b每个工会operaiton有两种可能的情况：

您试图团结从同一组项目。在这种情况下，什么都不做，并且不相交集合的数量保持不变。
您将来自两个不同集合的项目合并在一起，因此您基本上可以将两个集合合并为一个 - 将不相交集合的数量有效地减少一个。

由此我们可以得出结论，通过跟踪上述类型（2）的联合数量，很容易在每个时刻找到不相交集合的数目。
如果我们用succ_unions表示这个数字，那么每个点的集合总数为number_of_initial_sets - succ_unions。

来源

2015-06-17 22:05:17 amit

啊，经验教训，不要过时，谢谢。 – nitte93user3232918

@ user3232918你是最受欢迎的。很高兴我能帮上忙。 – amit

如果你需要知道的是不相交集数量而不是他的是，一种选择是将一个计数器变量添加到您的数据结构中，并计算出有多少不相交的集合。最初，它们有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 
}

希望这有助于！

来源

2015-06-17 22:04:30 templatetypedef

我希望我能接受两个答案。可悲的是，我不能。谢谢 – nitte93user3232918

查找不相交集合的数量

回答

相关问题