草庐IT

c++ - 找出不相交集的数量

coder 2024-02-16 原文

对于那些不熟悉 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。

我认为应该可行的选项。

  1. 在原来的后面附加新的集合，并销毁旧的集合。

  2. 在每个 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 操作有两种可能的情况:

  1. 您尝试将同一组中的项目组合在一起。在这种情况下，什么都不做，不相交集的数量保持不变。
  2. 您合并了来自两个不同集合的项目，因此您基本上将两个集合合并为一个 - 有效地将不相交集合的数量减少了一个。

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

关于c++ - 找出不相交集的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30903098/

amp找出parentintsectionc++algorithmdata-structuresdisjoint-setsdisjoint-union

有关c++ - 找出不相交集的数量的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  3. HBase Region 简介和建议数量&大小 - 2

    Region是HBase数据管理的基本单位,region有一点像关系型数据的分区。region中存储这用户的真实数据，而为了管理这些数据，HBase使用了RegionSever来管理region。Region的结构hbaseregion的大小设置默认情况下，每个Table起初只有一个Region，随着数据的不断写入，Region会自动进行拆分。刚拆分时，两个子Region都位于当前的RegionServer，但处于负载均衡的考虑，HMaster有可能会将某个Region转移给其他的RegionServer。RegionSplit时机：当1个region中的某个Store下所有StoreFile

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  6. ruby-on-rails - 如何找出拦截 'method_missing' 的内容 - 2

    使用Ruby1.8.6/Rails2.3.2我注意到在我的任何ActiveRecord模型类上调用的任何方法都返回nil而不是NoMethodError。除了烦人之外，这还破坏了动态查找器(find_by_name、find_by_id等)，因为即使存在记录，它们也总是返回nil。不从ActiveRecord::Base派生的标准类不受影响。有没有办法追踪在ActiveRecord::Base之前拦截method_missing的是什么？更新:切换到1.8.7后，我发现(感谢@MichaelKohl)will_paginate插件首先处理method_missing。但是will_pa

  7. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  8. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  9. ruby-on-rails - 设计中的 ArgumentError::RegistrationsController#new 错误的参数数量(2 代表 0..1) - 2

    我在关注RyanbatesRailsCast的devise和omniauth(第235集-devise-and-omniauth-revised)。当我尝试使用Twitter登录时，标题中不断出现错误。defself.new_with_session(params,session)ifsession["devise.user_attributes"]new(session["devise.user_attributes"],without_protection:true)do|user|user.attributes=paramsuser.valid?end完整跟踪:C:/Ruby20

  10. ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2

    我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc

随机推荐