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.
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
C++版本一
主要是记录移动次数，其实每个根结点都是最多移动一次的，所以记录移动次数把自己的加上父亲结点的就是移动总数了
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int N=10000+10;
int t,n,m,q,pre[N],ranksize[N],cnt[N];
int find(int x){
if(pre[x]==-1)return x;
int t=pre[x];
pre[x]=find(pre[x]);
cnt[x]+=cnt[t];
return pre[x];
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
pre[fx]=fy;
ranksize[fy]+=ranksize[fx];
cnt[fx]=1;
}
}
int main()
{
scanf("%d",&t);
for(int T=1;T<=t;T++){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
pre[i]=-1;
ranksize[i]=1;
cnt[i]=0;
}
printf("Case %d:\n",T);
char Q[10];
int a,b;
while(q--){
scanf("%s",Q);
if(Q[0]=='T'){
scanf("%d%d",&a,&b);
join(a,b);
}else{
scanf("%d",&a);
int ans=find(a);
cout << ans<<" "<<ranksize[ans]<<" "<< cnt[a]<< endl;
}
}
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include <stdio.h>
#include <string.h>
int size[10005], cnt[10005];
int asd;
class Union_Find_Set {
#define MAX_UNION_FIND_SET_SIZE 10005
public:
int setSize;
int father[MAX_UNION_FIND_SET_SIZE];
Union_Find_Set() {
setSize = 0;
}
Union_Find_Set(int x) {
setSize = x;
clear(x);
}
void clear(int x) {
for (int i = 0; i < x; i++) {
father[i] = i;
}
}
int getFather(int x) {
asd = cnt[x];
int ret = x, tmp;
while (ret != father[ret]) {
asd += cnt[father[ret]];
ret = father[ret];
}
int ttt = asd - cnt[ret];
while (x != father[x]) {
tmp = father[x];
father[x] = ret;
ttt -= cnt[x];
cnt[x] += ttt;
x = tmp;
}
return ret;
}
bool merge(int a, int b) {
a = getFather(a);
b = getFather(b);
if (a != b) {
father[a] = b;
cnt[a]++;
size[b] += (size[a] + 1);
return true;
} else {
return false;
}
}
int countRoot() {
int ret = 0;
for (int i = 0; i < setSize; i++) {
if (father[i] = i) {
ret++;
}
}
return ret;
}
};
Union_Find_Set ufs;
int main() {
int tt;
scanf("%d", &tt);
for (int jjjj = 1; jjjj <= tt; jjjj++) {
printf("Case %d:\n", jjjj);
int n, q, a, b;
char t;
scanf("%d%d", &n, &q);
ufs.clear(10005);
memset(size, 0, sizeof(size));
memset(cnt, 0, sizeof(cnt));
while (q--) {
getchar();
scanf("%c", &t);
if (t == 'T') {
scanf("%d%d", &a, &b);
ufs.merge(a, b);
} else if (t == 'Q') {
scanf("%d", &a);
int f = ufs.getFather(a);
printf("%d %d %d\n", f, size[f] + 1, asd);
}
}
}
return 0;
} C++版本三
这题是一题并查集，比较需要注意的是关于这个城市有几个球，球动了几次，是两个处理点，第一个有几个球是很好处理的，利用一个数组储存一开始n个城市每个城市有1个 球，再进行移动操作的时候，再加起来，把后者变成0.到时候查询城市，只需查询并查集的代表元素就可以了，而球的移动次数如何算了，我是使用了你连接的上级有几个，你就移动 几次的特点，因为不压缩路径的话，你每移动一次都会多一个上级，只要一直往上查询，直到查询到第一个元素，统计step就可以得出移动几次。 附上代码： 这题还要注意下用cin读入会TLE 用scanf就ac了
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define MAXN 1000005
int pre[MAXN];
int presum[MAXN];///这个城市有多少球
int unionsearch(int root)
{
int son,tmp;
son=root;
while(root!=pre[root])///寻找父节点，一层一层向上
{
root=pre[root];
}
/**while(root!=son)///路径压缩，就是先将原上级保持在tmp内，在把pre[son]指向父节点，然后再将tmp赋值给son
{tmp=pre[son];
pre[son]=root;///这个过程会不断的去压缩路径，来优化，防止算法退化为O(N)的查找
son=tmp;
}///其实可以以递归写
/**
来至CWL学长的代码：
int acfind(int x)
{
return pre[x]==x?x:pre[x]=acfind(pre[x]);
}
**/
return root;
}
int unionfinds(int root)
{
int son,tmp;
int step=0;
son=root;
while(root!=pre[root])///寻找父节点，一层一层向上
{
root=pre[root];
step++;
}
return step;
}
void unionjoin(int x,int y)///把x城市的球运到y城市
{
int a,b;
a=unionsearch(x);
b=unionsearch(y);
if(a!=b)
{
pre[a]=b;
presum[b]+=presum[a];
presum[a]=0;
}
}
int main()
{
int t,n,q;
char a;
int b,c;
while(~scanf("%d",&t))
{
for(int i=0;i<t;i++)
{
scanf("%d%d",&n,&q);
for(int j=1;j<=n;j++)///实现n个城市有1个球
presum[j]=1;
for(int j=1;j<=n;j++)///实现单个城市为单个集合
{
pre[j]=j;
}
printf("Case %d:\n",i+1);
for(int j=0;j<q;j++)
{getchar();
scanf("%c",&a);
if(a=='T')
{scanf("%d%d",&b,&c);
unionjoin(b,c);
}
if(a=='Q')
{scanf("%d",&b);
int d=unionsearch(b);
printf("%d %d %d\n",d,presum[d],unionfinds(b));
}
}
}
}
}
京公网安备 11010502036488号