杭电3635-Dragon Balls（并查集）

偏执的太偏执、 2022-08-04 12:36 16阅读 0赞

# Dragon Balls #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)**

Total Submission(s): 4582 Accepted Submission(s): 1747

Problem Description

Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together.  
![C308_1004_1.jpg][]  
His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities' dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls.  
Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.

Input

The first line of the input is a single positive integer T(0 < T <= 100).  
For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000).  
Each of the following Q lines contains either a fact or a question as the follow format:  
T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different.  
Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). (1 <= A, B <= N)

Output

For each test case, output the test case number formated as sample output. Then for each query, output a line with three integers X Y Z saparated by a blank space.

Sample Input

2
    3 3
    T 1 2
    T 3 2
    Q 2
    3 4
    T 1 2
    Q 1
    T 1 3
    Q 1

Sample Output

Case 1:
    2 3 0
    Case 2:
    2 2 1
    3 3 2

Author

possessor WC

Source

[2010 ACM-ICPC Multi-University Training Contest（19）——Host by HDU][2010 ACM-ICPC Multi-University Training Contest_19_Host by HDU]

题意：有N个球，标号1,2.3…原来分别在各自标号对应的城市1,2,3…后来经过了一些变换后现在让你球一些球的状态：

两个操作：

T A B 表示把A球所在的城市里所有球添加到B球所在的城市

Q A 表示 输出A所在的城市，A所在的城市里的球的个数，A转移的次数

**分析：**

可以想到是用并查集，前两个问题都很好解决，一个找根节点另一个找这棵树上总的元素个数，难的是第三个问题，怎么求转移的次数呢？

我们可以设一个数组，来记录，每次都要更新，显然如果在合并函数中来计算式很麻烦的，我们采用另一种方法，在合并函数中，我们只让转移的根节点加一，其他不管，在下一次合并之前我们要压缩路径，压缩的过程中，我们来更新转移次数，但是切记我们一定要从上向下更新，这一过程也只能用递归加回溯来实现了！

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int city[10100],per[10100],num[10100];
    int m,n,mov[10100];
    char s[3];
    void init()
    {
    	for(int i=1;i<=m;i++)
    	{
    		per[i]=i;
    		num[i]=1;
    		mov[i]=0;//初始化数组 
    	}
    }
    int find(int x)
    {
    //	int t=x;
    //	while(t!=per[t])
    //	t=per[t];
    //	int i=x,j;
    //	while(i!=t)
    //	{
    //		j=per[i];
    //		per[i]=t;
    //		i=j;
    //	}
    //	return t;//开始的时候配合下面注释掉的部分写的普通压缩路径 
    	if(x!=per[x])
    	{
    		int t=per[x];
    		per[x]=find(t);
    		mov[x]+=mov[t];//更新时，子节点的移动的次数等于他本身移动的次数加上父节点移动的次数 
    	}
    	return per[x];
    }
    void join(int x,int y)//合并两颗不同的数 
    {
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy)
    	{
    
    //		for(int i=1;i<=m;i++)
    //		{
    //			if(find(i)==fx)
    //			mov[i]++;
    //		}//这是我开始的想法，在join函数中直接更新，但是果断超时了 
    		per[fx]=fy;
    		num[fy]+=num[fx];
    		mov[fx]=1;//每次跟接待你只可能移动一次，所以只让根节点等于1便可 
    	}
    }
    int main()
    {
    	int N,a,b,cot=1;
    	scanf("%d",&N);
    	while(N--)
    	{
    		scanf("%d%d",&m,&n);
    		init();
    		printf("Case %d:\n",cot++);//控制格式 
    		for(int i=0;i<n;i++)
    		{
    			scanf("%s",s);//采用%S输入的好处是不用处理吸收回车符 
    			if(s[0]=='T')//两种不同的操作 
    			{
    				scanf("%d%d",&a,&b);
    				join(a,b);
    			}
    			else
    			{
    				scanf("%d",&a);
    				int t=find(a);//找到a的根节点 
    				printf("%d %d %d\n",t,num[t],mov[a]);
    			}
    		}
    	}
    return 0;
    }

[C308_1004_1.jpg]: /images/20220731/f21f3c8220d849edbd1cffc4a77c4905.png
[2010 ACM-ICPC Multi-University Training Contest_19_Host by HDU]: http://acm.hdu.edu.cn/search.php?field=problem&key=2010+ACM-ICPC+Multi-University+Training+Contest%A3%A819%A3%A9%A1%AA%A1%AAHost+by+HDU&source=1&searchmode=source