首页 > 代码库 > hdu 3172
hdu 3172
http://acm.hdu.edu.cn/showproblem.php?pid=3172
题意:输出每对朋友的关系网大小
并查集的时候维护一个数组记录根节点的大小即可,水题,这题坑在T组数据这个也要读到EOF,开始莫名其妙wa...
#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <queue>#include <cmath>#include <stack>#include <set>using namespace std;int fa[100005],sum[100005],cnt[100005];int find(int x){ if(fa[x]!=x){ int pre=fa[x]; fa[x]=find(fa[x]); sum[x]+=sum[pre]; } return fa[x];}int main(){ int T; while(~scanf("%d",&T)){ while(T--){ int n; scanf("%d",&n); for(int i=0;i<100005;i++){ fa[i]=i; cnt[i]=1; } memset(sum,0,sizeof(sum)); map <string,int> mp; int st=1; while(n--){ char s1[25],s2[25]; scanf("%s%s",s1,s2); if(!mp[s1])mp[s1]=st++; if(!mp[s2])mp[s2]=st++; int pa=find(mp[s1]); int pb=find(mp[s2]); if(pa!=pb){ fa[pa]=pb; cnt[pb]+=cnt[pa]; } printf("%d\n",cnt[pb]); } } } return 0;}
hdu 3172
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。