ZOJ:2833 Friendship（并查集+哈希）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2833

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.

题解： 格式错误了N次，以前的题都没卡这么死，这次最后一次输入没空行卡的很死，第一次学会这么写的方式，首先定义一个标记变量，还有手残了N次，另外由于M的值很大，如果不处理，果断超时，所以用到了哈希。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int bin[100001],sum[100001];
int n,m;
int findx(int x)
{
    int r=x;
    while(r!=bin[r])
        r=bin[r];
    int k,j=x;
    while(j!=r)
    {
        k=bin[j];
        bin[j]=r;
        j=k;
    }
    return r;
}
void merge(int x,int y)
{
    int fx=findx(x);
    int fy=findx(y);
    if(fx!=fy)
    {
        bin[fy]=fx;
        sum[fx]+=sum[fy];//根节点加上新加入集合的数目
    }
}
int main()
{
    char a[2];
    int flag=0,K=0,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(flag==1)
        {
            printf("
");
        }
        flag=1;
        printf("Case %d:
",++K);
        for(int i=1; i<=n; i++)
        {
            bin[i]=i;
            sum[i]=1;
        }
        while(m--)
        {
            scanf("%s",a);
            if(a[0]=='M')
            {
                scanf("%d%d",&x,&y);
                if(x!=y)
                {
                    merge(x,y);
                }
            }
            else if(a[0]=='Q')
            {
                scanf("%d",&x);
                printf("%d
",sum[findx(x)]);//这里我竟写错了，该剁手啊
            }
        }
    }
    return 0;
}