首页 > 代码库 > 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;}
View Code

 

hdu 3172