题意:n个点m次询问,两种操作:1.将含有龙珠i的集合加入含有龙珠j的集合中;2.查询龙珠i所在堆的编号,龙珠个数,龙珠i的搬运次数;
思路:并查集,数组分别维护关系、数量、搬运次数;
#include#include #include using namespace std;int n,m;int fa[500010],time[500010],num[500010];void init(){ for(int i=0;i<=n;i++) { fa[i]=i;num[i]=1;time[i]=0; }}int fin(int x){ if(fa[x]==x) return x; int j=fa[x]; fa[x]=fin(fa[x]); time[x]+=time[j];//累加搬移次数 return fa[x];}void combine(int a,int b){ int t1=fin(a); int t2=fin(b); if(t1!=t2) { fa[t1]=t2; num[t2]+=num[t1];//两个集合中的个数合并 time[t1]=1;//搬移次数置1 }}int main(){ char ch[5]; int i,j,k,t,a,b; scanf("%d",&t); for(j=1;j<=t;j++) { printf("Case %d:\n",j); scanf("%d%d",&n,&m); init(); for(i=0;i