题目链接：http://acm.swust.edu.cn/problem/856/
Description
There are N trees in a forest. At first, each tree contains only one node as its root. And each node is marked with a number.
You're asked to do the following two operations:
A X Y, you need to link X's root to Y as a direct child. If X and Y have already been in the same tree, ignore this operation.
B X, you need to output the maximum mark in the chain from X to its root (inclusively).
Input
The first line contains an integer T, indicating the number of followed cases. (1 <= T <= 20)
For each case, the first line contains two integers N and M, indicating the number of trees at beginning, and the number of operations follows, respectively. (1 <= N, M <= 100,000)
And the following line contains N integers, which are the marks of the N trees. (0 <= Mark <= 100,000)
And the rest lines contain the operations, in format A X Y, or B X, (0 <= X, Y < N).
Output
For each 'B X' operation, output the maximum mark.
Sample Input
|
1
5 5
5 4 2 9 1
A 1 2
A 0 4
B 4
A 1 0
B 1
|
|
1 5 |
题目大意：就是一个数组（下标从零开始），有对应的A,B操作，A a,b,是把a所在集合归并到b上，
若某一个集合已合并不进行操作，然B a,就是查询a集合中的最大值。
解题思路：运用并查集就是，注意a集合到b所在集合，并查集合并区分一下就可以了
代码如下：
#include <stdio.h>
int n, m, maxn, t, f[], cur[]; void init(){
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++){
scanf("%d", &cur[i]);
f[i] = i;
}
} int findset(int x){
maxn = cur[x];
if (f[x] == x) return x;
int y = findset(f[x]);
if (maxn > cur[x]) cur[x] = maxn;
else maxn = cur[x];
return f[x] = y;
} void mergy(){
int i, x, y;
char k[];
for (i = ; i < m; i++){
scanf("%s", k);
if (k[] == 'A'){
scanf("%d%d", &x, &y);
int a = findset(x), b = findset(y);
if (a != b) f[a] = y;//注意和传统并查集的区别
}
else{
scanf("%d", &x);
findset(x);
printf("%d\n", cur[x]);
}
}
} int main(){
scanf("%d", &t);
while (t--){
init();
mergy();
}
return ;
}