首页 > 代码库 > hdu 3635

hdu 3635

2024-08-04 16:35:11   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=3635

1-n个城市，对应放着编号1-n的龙珠。

两种操作

T A B 把编号A的龙珠所在城市内的全部龙珠放到有编号B的龙珠的城市内

Q A 查询编号A的龙珠的信息，输出三个数，A所在城市，A所在城市龙珠数目，A转移到该城市所用次数

思路：对球进行并查集维护，sum[a]表示a点移动到目前根的次数，每次合并的时候把A球根节点的sum设为1，这是并查集一个经典的操作，转移次数问题解决。A球所属城市的龙珠数目单开一个数组记录一下即可。所属城市就是根节点编号（这个点的球没有被合并过，所以球编号等于城市编号）

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <queue>#include <cmath>#include <stack>#include <set>using namespace std;int fa[10005],sum[10005],cnt[10005];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;    scanf("%d",&T);    for(int cas=1;cas<=T;cas++){        int n,q;        scanf("%d%d",&n,&q);        for(int i=0;i<=n;i++){            fa[i]=i;            cnt[i]=1;        }        memset(sum,0,sizeof(sum));        printf("Case %d:\n",cas);        while(q--){            char op[5];            scanf("%s",op);            if(op[0]==‘T‘){                int a,b;                scanf("%d%d",&a,&b);                int pa=find(a);                int pb=find(b);                if(pa!=pb){                    fa[pa]=pb;                    cnt[pb]+=cnt[pa];                    sum[pa]=1;                }            }            else{                int a;                scanf("%d",&a);                int rt=find(a);                printf("%d %d %d\n",rt,cnt[rt],sum[a]);            }        }    }    return 0;}
View Code

 

hdu 3635


联系
我们