[zoj 2833] Friendship

Friendship

---

Time limit: 3 Seconds Memory limit: 32768K
Total Submit: 908 Accepted Submit: 195

---

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.

Author: LIU, Yaoting

---

Problem Source: Zhejiang University Local Contest 2007, Preliminary

07校赛预赛的最后一道题目，也是由我负责作的，结果没出来，对不起大家啊T_T。比赛的时候用了set和map，但是这道题目数据量很大，这样会超时的。所以回去看了下书后改用disjoint set，而且内部是用森林的数据结构解决的而不用链表，主要还是担心速度的问题嘛。

#include
typedef struct
{
int p;
int r;
int v;
}NODE;

#define MAKE_SET(x) {(x).p = (x).v; (x).r = 1;}

#define MAXLEN 100001

NODE s [MAXLEN];

inline int FIND_SET(NODE s [], int x)
{
while ( s[x].v != s[x].p )
x = s[x].p;
return x;
}

inline void LINK(NODE &x, NODE &y)
{
if (x.r > y.r)
{
y.p = x.v;
x.r += y.r;
}
else
{
x.p = y.v;
y.r += x.r;
}
}

inline void UNION(NODE s [], int x, int y)
{
LINK(s[FIND_SET(s, x)], s[FIND_SET(s, y)]);
}

int main()
{
int n, m;
bool first = true;
int cc = 1;



while (scanf("%d %d", &n, &m) != EOF)
{
for (int i = 0; i < MAXLEN; ++i)
{
s[i].v = i;
MAKE_SET(s[i]);
}

bool second = true;

if (!first)
printf("\n");

while (m--)
{
char line;
char c;
scanf("%c %c", &line, &c);

if (c == 'M')
{
int x, y;
scanf("%d %d", &x, &y);

if (FIND_SET(s, x) != FIND_SET(s, y))
UNION(s, x, y);

}
else
{
if (second)
{
printf("Case %d:\n", cc);
second = false;
}

int q;
scanf("%d", &q);

if (s[q].p == s[q].v && s[q].r == 1)
{
printf("1\n");
continue;
}
int pp = FIND_SET(s, q);
printf("%d\n", s[pp].r);


}
}

first = false;
++cc;
}
return 0;
}