对于那些不熟悉 Disjoint-set 数据结构的人。
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
我正在努力寻找不。来自给定 friend 组及其关系的 friend 组。当然,毫无疑问,这可以使用 BFS/DFS 轻松实现。但我选择使用 disjoint set,我也倾向于查找该人所属的 friend 组等,而 disjoint-set 听起来当然适合这种情况。
我已经实现了不相交集数据结构,现在我需要找到它包含的不相交集的数量(这将给我组数)。
现在,我一直致力于实现如何有效地找到不相交集的数量,因为 friend 的数量可能大到 1 00 00 0。
我认为应该可行的选项。
在原来的后面附加新的集合,并销毁旧的集合。
在每个 union 中更改每个元素的父元素。
但是由于 friend 的数量很大,我不确定这是否是正确的方法,也许是否有任何其他有效的方法或者我应该继续实现上述任何方法。
这是我的代码以获取更多详细信息。(我还没有在这里实现计数不相交集)
//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;
}
最佳答案
在不相交集合数据结构中对两项 a,b
的每个 union 操作有两种可能的情况:
- 您尝试将同一组中的项目组合在一起。在这种情况下,什么都不做,不相交集的数量保持不变。
- 您合并了来自两个不同集合的项目,因此您基本上将两个集合合并为一个 - 有效地将不相交集合的数量减少了一个。
由此,我们可以得出结论,通过跟踪上述类型 (2) 的并集数,很容易找到每个时刻不相交集的数量。
如果我们用succ_unions
表示这个数字,那么每个点的集合总数就是number_of_initial_sets - succ_unions
。
关于c++ - 找出不相交集的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30903098/