A - Friendship
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, both beautiful and wise. Or perhaps a friend is like a ghost, whose spirit never dies. A friend is like a heart that goes strong until the end. Where would we be in this world if we didn't have a friend? - 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 use 'scanf()' and 'printf()' instead of 'cin' and 'cout' to avoid time limit exceed.
解答：
int fa[100001];
int num[100001];
int fine(int k)
{
while(k!=fa[k])
k=fa[k];
return k; //被调函数：寻找数链的根！
}
int su(int a,int b)
{
int x=fine(a);
int y=fine(b); //把两个集合联合起来！
if(x==y)
return 0; //如果两个集合具有共同的根，说明本身总数不用再相加！
if(num[x]<num[y])
{
int r=x;
x=y;
y=r;
} //比较两个数组的大小，把小的归于大集合！
fa[y]=x;
num[x]+=num[y]; //计算集合结点
}
#include<stdio.h> //主函数
#include<string.h> //头文件！
int main()
{
int a,b,d,e,f;
char c;
int i,s,t=1;
while(scanf("%d%d",&a,&b)!=EOF)
{
for(i=1;i<=a;i++)
{
fa[i]=i;
num[i]=1;
}if(t!=1) //注意：不能在后面加空格，因为最后一个输出没有空格！
printf("\n");
printf("Case %d:\n",t++); //计算完成事件个数
while(b--)
{
getchar(); //吃掉前面的空格
scanf("%c",&c);
if(c=='M')
{
scanf("%d%d",&e,&f);
su(e,f);
}
else if(c=='Q')
{
scanf("%d",&d);
s=fine(d);
printf("%d\n",num[s]); //打印这个集合包含的个数，不能一个一个判断，会超时
}
}
}
return 0; //结束
}