查找不相交集合的数量

Question

对于不熟悉不相交集合数据结构的人来说。

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

- nitte93

Answer 1

在不相交集数据结构中，对两个项a,b执行每个联合操作有两种可能情况：

1. 您试图将来自同一集合的项目合并。在这种情况下，不做任何操作，并且不相交集的数量保持不变。
2. 您将来自两个不同集合的项目合并，因此您实际上将两个集合合并为一个-从而将不相交集的数量减少了一个。

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

- amit

---

这种方法与保持联合操作总数的计数有什么不同吗？比如，初始时count=1，每次调用union时我们都会增加count。 - Saurabh Rana

Answer 2

如果你只需要知道不相交集合的数量而不需要知道它们是什么，一种方法是在数据结构中添加一个计数器变量，用来计算不相交集合的数量。最初，有 n 个单独的元素，因此就有 n 个不相交的集合。每次执行并集操作时，如果两个元素没有相同的代表，则说明你正在将两个不相交的集合合并为一个，因此可以减少计数器的值。代码示例如下：

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
}

希望这能帮到你！

- templatetypedef

---

好的回答！想要为它点赞！！！！！！！！ - alan23273850