Description
| A friend is like a flower, a rose to be exact, Or maybe like a brand new gate that never comes unlatched. A friend is like an owl, A friend is like a heart that goes - By Emma Guest |
Now you've grown up, it's time to make friends. The friends you make in university are the friends you make for life. You will be proud if you have many friends.
Input
There are multiple test cases for this problem.
Each test case starts with a line containing two integers N, M (1 <= N <= 100'000, 1 <= M <= 200'000), representing that there are totally N persons (indexed from 1 to N) and M operations, then M lines with the form "M a b" (without quotation) or "Q a" (without
quotation) follow. The operation "M a b" means that person a and b make friends with each other, though they may be already friends, while "Q a" means a query operation.
Friendship is transitivity, which means if a and b, b and c are friends then a and c are also friends. In the initial, you have no friends except yourself, when you are freshman, you know nobody, right? So in such case you have only one friend.
Output
For each test case, output "Case #:" first where "#" is the number of the case which starts from 1, then for each query operation "Q a", output a single line with the number of person a's friends.
Separate two consecutive test cases with a blank line, but Do NOT output an extra blank line after the last one.
Sample Input
3 5
M 1 2
Q 1
Q 3
M 2 3
Q 2
5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4
Sample Output
Case 1:
2
1
3
Case 2:
1
1
3
1
4
Notes
This problem has huge input and output data, please
说实话，这是水题，可我TLE了好多次，用了压缩路径依然不过，当时很郁闷
一同学没用压缩路径竟然过了，我就很无语，看看代码，比较了树的大小，然后我加上，竟然过了。。。
好吧，为了验证，我用了各种非压缩方法，加上比较，依然过，如果比赛的话，我不是很惨。。。
经验很重要啊
#include<stdio.h>
int n , m, num[100001];
int father[100001];
void init(){
for(int i = 1; i <=n ; i++)
{
father[i] = i;
num[i]=1;
}
}
int find(int x){
while(x!=father[x])
x=father[x];
return x;
}
void Union(int x , int y){
int fx = find(x);
int fy = find(y);
if(fx>fy)
{
num[fx]+=num[fy];
father[fy]=father[fx];
}
if(fx<fy)
{
num[fy]+=num[fx];
father[fx]=father[fy];
}
}
int main()
{
int u=0,p,aa[100110];
char c;
while(scanf("%d%d%*c",&n,&m)!=EOF)
{
u++;
p=0;
init();
if(n==0&&m==0)break;
while(m--)
{
int a,b,v;
scanf("%c",&c);
if(c=='M')
{
scanf("%d%d%*c",&a,&b);
Union(a,b);
}
if(c=='Q')
{
scanf("%d%*c",&v);
aa[p++]=num[find(v)];
}
}
if(u!=1)
printf("\n");
printf("Case %d:\n",u);
for(int i=0;i<p;i++)
printf("%d\n",aa[i]);
}
}