HDU 并查集 - 3172 Virtual Friends - c++编程基础

TOP

HDU 并查集 - 3172 Virtual Friends

2015-11-21 01:01:18 来源: 作者: 【大中小】浏览:1次

并查集题目，并的意思就是将两个不同类别的集合合并到一起，类似于两棵树合并；查的意思就是找到这个点所属集合的根节点。基本上并查集题目都是在大体架构上面加一些东西即可。并查集代码模板在这里点击打开链接。

这一题为了找到输入的两个人组成的社交网络人数，也就是统计这两个人与前面的人组成的集合中有多少元素。我们加一个辅助数组sum，当两个集合并时，我们将父节点对应下标的sum值加上子节点的sum值，表达这个集合有多少元素。

#include
  
   
#include
   
     #include
    
      #include
      using namespace std; #define MAX 100000 int total; map
      
       A; int pa[MAX],sum[MAX]; int find_set(int x){ if(x==pa[x]) return x; pa[x]=find_set(pa[x]); return pa[x]; } void union_set(int x,int y){ x = find_set(x); y = find_set(y); if(x!=y){ pa[x]=y; sum[y]+=sum[x]; } } int main(){ int n,m; string a,b; while(scanf("%d",&n)!=EOF){ while(n--){ total=0; A.clear(); scanf("%d",&m); while(m--) { cin>>a>>b; if(A.find(a)==A.end()) { total++; A[a]=total; pa[total]=total; sum[total]=1; } if(A.find(b)==A.end()) { total++; A[b]=total; pa[total]=total; sum[total]=1; } union_set(A[a],A[b]); int ans=find_set(A[a]); printf("%d\n",sum[ans]); } } } }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：[LeetCode] House Robber II	下一篇：[LeetCode][Java] Unique Paths

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: